Klee's measure problem made easy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages410-419
Number of pages10
DOIs
StatePublished - 2013
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

Keywords

  • Boxes
  • Computational geometry
  • Volume

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Klee's measure problem made easy'. Together they form a unique fingerprint.

Cite this