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.

A set of rectangular ranges ('trellis') whose area has to be measured.

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 edit

In 1977, Victor Klee considered the following problem: given a collection of n intervals in the real line, compute the length of their union. He then presented an algorithm to solve this problem with computational complexity (or "running time")   — see Big O notation for the meaning of this statement. This algorithm, based on sorting the intervals, was later shown by Michael Fredman and Bruce Weide (1978) to be optimal.

Later in 1977, Jon Bentley considered a 2-dimensional analogue of this problem: given a collection of n rectangles, find the area of their union. He also obtained a complexity   algorithm, now known as Bentley's algorithm, based on reducing the problem to n 1-dimensional problems: this is done by sweeping a vertical line across the area. Using this method, the area of the union can be computed without explicitly constructing the union itself. Bentley's algorithm is now also known to be optimal (in the 2-dimensional case), and is used in computer graphics, among other areas.

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 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 asymptotic running time for the common special cases where d is 3 or 4.

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 edit

The only known lower bound for any d is  , and optimal algorithms with this running time are known for d=1 and d=2. The Chan algorithm provides an upper bound of   for d ≥ 3, so for d ≥ 3, it remains an open question whether faster algorithms are possible, or alternatively 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 (for example, when the input coordinates are integers within a bounded range) remains open.

The 1D Klee's measure problem (union of intervals) can be solved in   where p denotes the number of piercing points required to stab all intervals[1] (the union of intervals pierced by a common point can be calculated in linear time by computing the extrema). Parameter p is an adaptive parameter that depends on the input configuration, and the piercing algorithm[2] yields an adaptive algorithm for Klee's measure problem.

See also edit

References and further reading edit

Important papers edit

  • Klee, Victor (1977), "Can the measure of   be computed in less than   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  ", 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.

Secondary literature edit

References edit

  1. ^ "Adaptive Computational Geometry", F. Nielsen, pdf
  2. ^ "Fast stabbing of boxes in high dimensions", F. Nielsen, Theoretical Computer Science Volume 246, Issues 1–2, 6 September 2000, Pages 53-72 pdf