Klee's measure problem
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd.
The problem is named after Victor Klee, who gave an algorithm for computing the length of a union of intervals (the case d = 1) which was later shown to be optimally efficient in the sense of computational complexity theory. The computational complexity of computing the area of a union of 2-dimensional rectangular ranges is now also known, but the case d ≥ 3 remains an open problem.
History and algorithms
In 1977,
Later in 1977,
These two problems are the 1- and 2-dimensional cases of a more general question: given a collection of n d-dimensional rectangular ranges, compute the measure of their union. This general problem is Klee's measure problem.
When generalized to the d-dimensional case, Bentley's algorithm has a running time of . 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 subproblems. In 1981, Jan van Leeuwen and Derek Wood improved the running time of this algorithm to for d ≥ 3 by using dynamic quadtrees.
In 1988, Mark Overmars and Chee Yap proposed an algorithm for d ≥ 3. Their algorithm uses a particular data structure similar to a
In 2013, Timothy M. Chan developed a simpler algorithm that avoids the need for dynamic data structures and eliminates the logarithmic factor, lowering the best known running time for d ≥ 3 to .
Known bounds
The only known
The 1D Klee's measure problem (union of intervals) can be solved in where p denotes the number of piercing points required to
See also
- Convex volume approximation, an efficient algorithm for convex bodies
References and further reading
Important papers
- Klee, Victor (1977), "Can the measure of be computed in less than steps?", 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 ", S2CID 16493364.
- MR 0632450.
- 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), 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, S2CID 11648588.
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. (Accessed November 8, 2005, when the last update was July 31, 1998.)