볼록체적 근사치

알고리즘 분석에서 여러 저자들이 고차원 볼록체의 부피 연산을 연구했는데, 이 문제는 결합기 열거에서 다른 많은 문제들을 모델링하는 데에도 사용될 수 있다.종종 이러한 작품들은 블랙박스 연산 모델을 사용하며, 블랙박스 모델은 볼록한 폴리토프의 정점이나 면의 명시적인 나열이 아니라, 점이 볼록체 내부 또는 외부에 있는지 시험하기 위해 서브루틴에 의해 입력이 주어진다.이 모델에서 어떤 결정론적 알고리즘도 정확한 근사치를 달성할 수 없으며,^[1][2] 얼굴이나 정점의 명시적 나열에도 문제는 #P-hard라고 알려져 있다.^[3]그러나 마틴 다이어의 공동작품인 앨런 M. Frieze와 Ravindran Kannan은 문제에 대해 무작위화된 다항식 시간 근사 체계를 제공함으로써 랜덤화 알고리즘과 결정론적 알고리즘의 능력 사이의 뚜렷한 대조를 제공했다.^[4]

논문의 주요 결과는 멤버십 오라클의 존재를 가정하여 $n{\displaystyle }$ ${\displaystyle$$\varepsilon }$ 볼록체 $K{\displaystyle }$ ${\displaystyle$ $K$$}$의 부피에 대한 $근사치$를 찾기 위한 임의 알고리즘이다.알고리즘은 $n{\displaystyle }$ ${\displaystyle n}$의$$다항식$,$ K {\$displaystyle K}$ $및$ 1 /${\displaystyle \epsilon }$ ${\displaystyle 1/\varipsilon }$의 치수에 의해 제한되는 시간이 걸린다$.$ 알고리즘은 두 가지 아이디어를 결합한다.

• 마르코프 체인 몬테 카를로(MCMC) 방법을 사용하면 주어진 볼록체 내에서 거의 임의로 분포된 점을 생성할 수 있다.알고리즘의 기본 체계는 $n{\displaystyle }$ ${\displaystyle n}$ -차원$$ 입방체로 구성된 그리드를 배치하고$$ 이러한 입방체 위에 무작위 보행을 수행하여 $K{\displaystyle }$ ${\displaystyle K}$ 내에서 거의 균일한 샘플링이다.마르코프 사슬을 빠르게 혼합하는 이론을 사용함으로써, 무작위 걷기가 거의 균일한 분포로 정착되려면 다항식 시간이 걸린다는 것을 보여준다.^[4]
• 거부 샘플링을 사용하면 두 볼록한 신체의 체적이 서로 작은 요인 내에 있을 때 서로 내포된 체적의 체적을 비교할 수 있다.기본이념은 두 신체의 바깥쪽 안에서 임의의 점을 발생시키고, 그 점들이 얼마나 자주 내측에도 있는가를 세어 보는 것이다.

주어진 볼록한 신체는 일련의 중첩된 신체에 의해 대략적으로 추정될 수 있으며, 결국 알려진 볼륨 중 하나에 도달할 수 있으며, 이 접근방식은 이 시퀀스의 각 단계에서 볼륨이 변화하는 인자를 추정하는 데 사용된다.이러한 요소들을 곱하면 원체의 대략적인 부피를 알 수 있다.

이 작품은 작가들에게 1991년 풀커슨상을 수여했다.^[5]

개선사항

이 알고리즘의 시간은 다항식이지만 지수가 높다.후속 저자들은 같은 문제에 대해 마르코프 체인을 더 빨리 혼합하여 제공함으로써 이 방법의 실행 시간을 향상시켰다.^[6][7][8][9]

일반화

다항 시간 근사성 결과는 물체의 결합과 교차점과 같은 보다 복잡한 구조로 일반화되었다.^[10]이것은 Klee의 측정 문제와 관련이 있다.

참조