TY - GEN
T1 - Klee's measure problem made easy
AU - Chan, Timothy M.
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - We present a new algorithm for a classic problem in computational geometry, Klee's measure problem: given a set of n axis-parallel boxes in d-dimensional space, compute the volume of the union of the boxes. The algorithm runs in O(nd/2) time for any constant d ≥ 3. Although it improves the previous best algorithm by "just" an iterated logarithmic factor, the real surprise lies in the simplicity of the new algorithm. We also show that it is theoretically possible to beat the O(nd/2) time bound by logarithmic factors for integer input in the word RAM model, and for other variants of the problem. With additional work, we obtain an O(nd/3 polylog n)-time algorithm for the important special case of orthants or unit hypercubes (which include the so-called "hypervolume indicator problem"), and an O(n(d+1)/3 polylog n)-time algorithm for the case of arbitrary hypercubes or fat boxes, improving a previous O(n (d+2)/3)-time algorithm by Bringmann.
AB - We present a new algorithm for a classic problem in computational geometry, Klee's measure problem: given a set of n axis-parallel boxes in d-dimensional space, compute the volume of the union of the boxes. The algorithm runs in O(nd/2) time for any constant d ≥ 3. Although it improves the previous best algorithm by "just" an iterated logarithmic factor, the real surprise lies in the simplicity of the new algorithm. We also show that it is theoretically possible to beat the O(nd/2) time bound by logarithmic factors for integer input in the word RAM model, and for other variants of the problem. With additional work, we obtain an O(nd/3 polylog n)-time algorithm for the important special case of orthants or unit hypercubes (which include the so-called "hypervolume indicator problem"), and an O(n(d+1)/3 polylog n)-time algorithm for the case of arbitrary hypercubes or fat boxes, improving a previous O(n (d+2)/3)-time algorithm by Bringmann.
KW - Boxes
KW - Computational geometry
KW - Volume
UR - http://www.scopus.com/inward/record.url?scp=84893469130&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893469130&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2013.51
DO - 10.1109/FOCS.2013.51
M3 - Conference contribution
AN - SCOPUS:84893469130
SN - 9780769551357
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 410
EP - 419
BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Y2 - 27 October 2013 through 29 October 2013
ER -