A (slightly) faster algorithm for klee's measure problem

ABSTRACT

Given n axis-parallel boxes in a fixed dimension d ≥ 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(n^d/2 log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time n^d/22^O(log^*n), where log^* denotes the iterated logarithm.

For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(n^d/2 log^d/2-1 n), ignoring log\log n factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.

REFERENCES

• 1: Pankaj K. Agarwal , Haim Kaplan , Micha Sharir, Computing the volume of the union of cubes, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247121]
• 2: I. Baran, E.D. Demaine, and M. Patraşcu. Subquadratic algorithms for 3SUM. In Proc. 9th Workshop Algorithms Data Struct. Lect. Notes Comput. Sci., vol. 3608, Springer-Verlag, pages 409--421, 2005.
• 3: Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
• 4: J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19:473--484, 1998.
• 5: Sergio Cabello , Panos Giannopoulos , Christian Knauer , Günter Rote, Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.836-843, January 20-22, 2008, San Francisco, California
• 6: T.M. Chan. Geometric applications of a randomized optimization technique. Discrete Comput. Geom. 22:547--567, 1999.
• 7: Timothy M. Chan, Semi-Online Maintenance of Geometric Optima and Measures, SIAM Journal on Computing, v.32 n.3, p.700-716, 2003 [doi>10.1137/S0097539702404389]
• 8: Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250877]
• 9: L.P. Chew, D. Dor, A. Efrat, and K. Kedem. Geometric pattern matching in d-dimensional space. Discrete Comput. Geom. 21:257--274, 1999.
• 10: Amitava Datta , Hans-Peter Lenhof , Christian Schwarz , Michiel Smid, Static and dynamic algorithms for k-point clustering problems, Journal of Algorithms, v.19 n.3, p.474-503, Nov. 1995 [doi>10.1006/jagm.1995.1048]
• 11: Paul F. Dietz, Optimal Algorithms for List Indexing and Subset Rank, Proceedings of the Workshop on Algorithms and Data Structures, p.39-46, August 17-19, 1989
• 12: David P. Dobkin , David Eppstein , Don P. Mitchell, Computing the discrepancy with applications to supersampling patterns, ACM Transactions on Graphics (TOG), v.15 n.4, p.354-376, Oct. 1996 [doi>10.1145/234535.234536]
• 13: Adrian Dumitrescu , Joseph S. B. Mitchell , Micha Sharir, Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles, Discrete & Computational Geometry, v.31 n.2, p.207-227, February 2004 [doi>10.1007/s00454-003-0729-3]
• 14: D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. Discrete Comput. Geom.11:321--350, 1994.
• 15: David Eppstein , S. Muthukrishnan, Internet packet filter management and rectangle geometry, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.827-835, January 07-09, 2001, Washington, D.C., United States
• 16: J. Erickson. Klee's measure problem. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html, 1998.
• 17: Gudmund Skovbjerg Frandsen , Johan P. Hansen , Peter Bro Miltersen, Lower bounds for dynamic algebraic problems, Information and Computation, v.171 n.2, p.333-349, December 15, 2001 [doi>10.1006/inco.2001.3046]
• 18: Michael L. Fredman , Bruce Weide, On the complexity of computing the measure of ∪[a_i,b_i], Communications of the ACM, v.21 n.7, p.540-544, July 1978 [doi>10.1145/359545.359553]
• 19: Sariel Har-Peled , Vladlen Koltun , Dezhen Song , Ken Goldberg, Efficient algorithms for shared camera control, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777803]
• 20: Haim Kaplan , Natan Rubin , Micha Sharir , Elad Verbin, Counting colors in boxes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.785-794, January 07-09, 2007, New Orleans, Louisiana
• 21: V. Klee. Can the measure of ∪n/1{a_i, b_i} be computed in less than O(n log n) steps? Amer. Math. Monthly 84:284--285, 1977.
• 22: J. van Leeuwen and D. Wood. The measure problem for rectangular ranges in d-space. J. Algorithms
• 23: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 24: Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
• 25: J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10:157--182, 1993.
• 26: J. Nesetril and S. Poljak. On the complexity of the subgraph problem.Commen. Math. Univ. Carol. 26: 415--419, 1985.
• 27: Mark H. Overmars , Chee-Keng Yap, New upper bounds in Klee's measure problem, SIAM Journal on Computing, v.20 n.6, p.1034-1045, Dec. 1991 [doi>10.1137/0220065]
• 28: John H. Reif , Stephen R. Tate, On dynamic algorithms for algebraic problems, Journal of Algorithms, v.22 n.2, p.347-371, Feb. 1997 [doi>10.1006/jagm.1995.0807]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
boxes, data structures, union of geometric objects