Klee의 측도

계산기하학에서, Klee의 측정 문제는 (다차원) 직사각형 범위의 결합의 측정이 얼마나 효율적으로 계산될 수 있는지를 결정하는 문제이다.여기서 d차원 직사각형 범위는 R의^d 서브셋인 실수 d구간의 데카르트 곱으로 정의된다.

이 문제는 나중에 계산 복잡도 이론의 의미에서 최적으로 효율적인 것으로 증명된 구간 결합의 길이 계산 알고리즘을 제공한 빅터 클리의 이름을 따서 명명되었다.2차원 직사각형 범위의 결합 면적을 계산하는 계산 복잡성도 현재 알려져 있지만, 사례 d 3 3은 여전히 미해결 문제로 남아 있다.

이력 및 알고리즘

1977년에 Victor Klee는 다음과 같은 문제를 고려했습니다.실제 라인에 n개의 구간이 모이면 합계의 길이를 계산합니다.그런 다음 이 문제를 계산 복잡도(또는 "실행 $시간{\displaystyle }$")${\displaystyle }$O(${\displaystyle n}$ log${\$ )(\$displaystyle O(n\$ n)}$$로 해결하는 알고리즘을 제시했습니다.이 문장의 의미는 빅 O$$표기법을 참조하십시오.이 알고리즘은 구간의 정렬에 기초해 나중에 마이클 프레드먼과 브루스 와이드(1978)에 의해 최적이라는 것이 증명되었다.

그 후 1977년 존 벤틀리는 이 문제의 2차원 유추에 대해 검토했습니다. 즉, n개의 직사각형의 집합이 주어지면 합체 면적을 구하십시오.또한 문제를 n개의 1차원 문제로 줄임으로써 현재 Bentley 알고리즘으로 알려진 복잡도 O${\displaystyle (n}$ log${\displaystyle n}$n$)$ {$displaystyle$ O$(n\log$ n$)}$ 알고리즘도$$ 얻었습니다.이 알고리즘은 이 영역에 걸쳐 수직선을 그리면 됩니다.이 방법을 사용하면 결합 자체를 명시적으로 구성하지 않고도 결합 면적을 계산할 수 있다.또한 Bentley의 알고리즘은 현재 최적의 것으로 알려져 있으며(2차원의 경우) 컴퓨터 그래픽스 등에 사용되고 있습니다.

이 두 가지 문제는 보다 일반적인 질문의 1차원 및 2차원 사례이다. 즉, n개의 d차원 직사각형 범위 모음이 주어지면 결합의 측정값을 계산한다.이 일반적인 문제는 Klee의 측정 문제입니다.

d차원 케이스로 일반화하면 Bentley 알고리즘의 실행시간은 $O{\displaystyle (n^{}}$d - ${\displaystyle 1}$ log${\displaystyle n}$n $)(\display$ O$(n^{d-1}\log$ n$)$입니다.이는 d차원 문제를 n(d-1)차원 문제로 분해할 뿐 하위 문제를 더 분해하지 않기 때문에 최적이 아닌 것으로 판명되었다.1981년 Jan van Leeuwen과 Derek Wood는 동적 쿼드 트리를 사용하여 이 알고리즘의 실행 시간을 dµ3의${\displaystyle }$O ($n$ d${\displaystyle {}^{}}$-${\displaystyle {}^{}{1}^{}}$)$$($n$ $displaystyle$ O$(n^{d-1})$

1988년 Mark Overmars와 Chee Yap은 d 3 3의${\displaystyle }$O ( ${\displaystyle n^{}}$ d${\displaystyle {}^{}}$/ ${\displaystyle 2}$ log${\displaystyle n}$n$$) \ $displaystyle$O ( $n$^ {$d$ /$2$ \ $log$n )알고리즘을$$ $제안$했습니다.이들의 알고리즘은 kd-tree와 유사한 특정 데이터 구조를 사용하여 문제를 2차원 구성요소로 분해하고 이러한 구성요소를 효율적으로 집계합니다. 2차원 문제 자체는 트렐리스 구조를 사용하여 효율적으로 해결합니다.Bentley 알고리즘보다 점근적으로 빠르지만 데이터 구조가 훨씬 더 많은 공간을 사용하기 때문에 n 또는 d가 큰 문제에만 사용됩니다.1998년, Bogdan Chlebus는 d가 3 또는 4인 일반적인 특수한 경우에 동일한 점근적 실행 시간을 갖는 더 단순한 알고리즘을 제안했다.

2013년에는 티모시 M.Chan은 동적 데이터 구조의 필요성을 배제하고 로그 계수를 배제하는 단순한 알고리즘을 개발하여 d † $3$의 가장 잘 알려진 실행 시간을${\displaystyle }$O (${\displaystyle n^{}}$d /${\displaystyle {}^{}{2\mathrm{}}^{}}$)$$(\$display style$O ($n^{d/$2$\}))$로 낮춥니다.

알려진 한계

d에 대해 알려진 하한은${\displaystyle \delta }$ (${\displaystyle n}$ log${\displaystyle \delta }$n$$) {$displaystyle \Omega (n\log$ n$)\}$뿐이며, 이 실행 시간을 갖는 최적의 알고리즘은 d=1 및 d=2에 대해 알려져 있습니다.Chan 알고리즘은 d µ 3에 대해 O${\displaystyle (n^{}}$d /$)$의 $상한{\displaystyle }$(\$displaystyle$ O$(n^{d/2})$을 제공하므로 d µ 3에 대해서는 보다 빠른 알고리즘이 가능한지, 또는 보다 엄격한 하한을 증명할 수 있는지 여부는 미해결 상태로 남아 있습니다.특히 알고리즘의 실행 시간이 d에 의존해야 하는지 여부는 열린 상태로 유지됩니다.또한 특수한 경우(예를 들어 입력 좌표가 경계 범위 내의 정수인 경우)를 처리할 수 있는 더 빠른 알고리즘이 있는지에 대한 질문은 여전히 남아 있습니다.

1D Klee의 측정 문제(간격의 결합)는 O${\displaystyle (n}$ log ${\displaystyle }$ $)(\displaystyle$ O$(n\log$ p$))$로 해결할 수 있습니다. 여기서 p는 모든 간격을^[1] 찌르는 데 필요한 관통점 수를 나타냅니다(공통점에 의해 관통된 간격의 결합은 극단값을 계산하여 선형 시간으로 계산할 수 있습니다).파라미터 p는 입력 구성에 따라 달라지는 적응형 파라미터이며 피어싱^[2] 알고리즘은 Klee의 측정 문제에 대한 적응형 알고리즘을 생성합니다.

「 」를 참조해 주세요.

• 볼록체의 효율적인 알고리즘인 볼록 체적 근사

참고 자료 및 추가 자료

중요 서류

• 를 클릭합니다Klee, Victor (1977), "Can the measure of ${\displaystyle \cup [a_{i},b_{i}]}$ be computed in less than ${\displaystyle O(n\log n)}$ steps?", American Mathematical Monthly, 84 (4): 284–285, doi:10.2307/2318871, JSTOR 2318871, MR 0436661.
• 를 클릭합니다Bentley, Jon L. (1977), Algorithms for Klee's rectangle problems, Unpublished notes, Computer Science Department, Carnegie Mellon University.
• 를 클릭합니다Fredman, Michael L.; Weide, Bruce (1978), "The complexity of computing the measure of ${\displaystyle \cup [a_{i},b_{i}]}$", Communications of the ACM, 21 (7): 540–544, doi:10.1145/359545.359553, MR 0495193, S2CID 16493364.
• 를 클릭합니다van Leeuwen, Jan; Wood, Derick (1981), "The measure problem for rectangular ranges in d-space", Journal of Algorithms, 2 (3): 282–300, doi:10.1016/0196-6774(81)90027-4, hdl:1874/15897, MR 0632450.
• 를 클릭합니다Overmars, Mark H.; Yap, Chee-Keng (1991), "New upper bounds in Klee's measure problem", SIAM Journal on Computing, 20 (6): 1034–1045, doi:10.1137/0220065, hdl:1874/16614, MR 1135747.
• 를 클릭합니다Chlebus, Bogdan S. (1998), "On the Klee's measure problem in small dimensions", Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM-98), Lecture Notes in Computer Science, vol. 1521, Berlin: Springer-Verlag, pp. 304–311, doi:10.1007/3-540-49477-4_22, ISBN 978-3-540-65260-1.
• 를 클릭합니다Chan, Timothy M. (2013), "Klee's measure problem made easy", Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS) (PDF), pp. 410–419, CiteSeerX 10.1.1.643.26, doi:10.1109/FOCS.2013.51, ISBN 978-0-7695-5135-7, S2CID 11648588.

이차 문헌

• 프랑코 P. 프리파타와 미카엘 1세 Shamos(1985년).계산기하학(스프링거-벨라그, 베를린)
• Jeff Erickson 교수의 컴퓨터 기하학 미해결 문제 목록에 있는 Klee's Measure Problem. (2005년 11월 8일 최종 업데이트는 1998년 7월 31일)

레퍼런스