Klee's measure problem

From Wikipedia, the free encyclopedia

In computational geometry, Klee's measure problem is as follows: Given a set of d-dimensional rectangular ranges, how efficiently can we compute the measure of their union? It is (as of 2006) an open problem.

Contents 1 History 2 Current state 3 References and further reading 3.1 Important papers 3.2 Secondary literature

[edit] History

Victor Klee originally formulated the problem in 1977 in the 1-dimensional case: Given a set of n intervals on the real line, compute the length of their union. He gave an O(nlogn) algorithm (see Big O notation) based on sorting the intervals, which was shown in 1978 by Michael Fredman and Bruce Weide to be optimal.

Later in 1977, Jon Bentley considered the 2-dimensional version of the problem: Given a set of n rectangles, find the area of their union. He proposed an O(nlogn) algorithm, now known as Bentley's algorithm, that decomposes the 2-dimensional problem into n 1-dimensional problems by sweeping a vertical line across the area, and is thereby able to find the area of the union without explicitly constructing the union itself. This algorithm is optimal in the 2-dimensional case, and is used in computer graphics, among other areas.

When generalized to the d-dimensional case, Bentley's algorithm has a running time of O(n^{d − 1}logn). This turns out not to be optimal, because it only decomposes the d-dimensional problem into n (d-1)-dimensional problems, and does not further decompose those. In 1981, Jan van Leeuwen and Derek Wood somewhat improved the running time of this algorithm to O(n^{d − 1}) for by using dynamic quadtrees.

In 1988, Mark Overmars and Chee Yap proposed an O(n^{d / 2}logn) algorithm for which is currently (as of 2006) the fastest known. Their algorithm uses a particular data structure similar to a kd-tree to decompose the problem into 2-dimensional components and aggregate those components efficiently; the 2-dimensional problems themselves are solved efficiently using a trellis structure. Although asymptotically faster than Bentley's algorithm, its data structures use significantly more space, so it is only used in problems where either n or d is large. In 1998, Bogdan Chlebus proposed a simpler algorithm with the same running time for the common special cases where d is 3 or 4.

[edit] Current state

The only known lower bound for any d is Ω(nlogn). The Overmars-Yap algorithm provides an upper bound of O(n^{d / 2}logn), so for , it remains an open question whether faster algorithms are possible, or alternately whether tighter lower bounds can be proven. In particular, it remains open whether the algorithm's running time must depend on d. In addition, the question of whether there are faster algorithms that can deal with special cases remains open (for example, when there is a bound on the scale of the ranges).

[edit] References and further reading

[edit] Important papers

• Victor Klee (1977). Can the measure of be computed in less than O(nlogn) steps? American Mathematical Monthly 84: 284-285.
• Jon L. Bentley (1977). Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University.
• Michael L. Fredman and Bruce Weide (1978). The complexity of computing the measure of . Communications of the ACM 21: 540-544.
• Jan van Leeuwen and Derick Wood (1981). The measure problem for rectangular ranges in d-space. Journal of Algorithms 2: 282-300.
• Mark H. Overmars and Chee-Keng Yap (1988). New upper bounds in Klee's measure problem. Extended abstract. Rijksuniversiteit Utrecht Technical Report RUU-CS-88-22. Full version published in SIAM Journal of Computing 20(6): 1034-1045 (1991). (PDF of the tech report version.)
• Bogdan S. Chlebus (1998). On the Klee's measure problem in small dimensions. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM-98) (Jasná, Slovakia, November 21-27, 1998). Also published in Springer Lecture Notes in Computer Science 1521 (Springer-Verlag, Berlin, 1998).

[edit] Secondary literature

• Franco P. Preparata and Michael I. Shamos (1985). Computational Geometry (Springer-Verlag, Berlin).
• Klee's Measure Problem, from Professor Jeff Erickson's list of open problems in computational geometry. (Last updated July 31, 1998; accessed November 8, 2005.)