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

作者：Chan Timothy M^*

来源：Computational Geometry-Theory and Applications, 2010, 43(3): 243-250.

DOI：10.1016/j.comgeo.2009.01.007

• Union of geometric objects
• Boxes
• Volume
• Data structures

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/2)2(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.

• 出版日期2010-4