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

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

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(nd/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/22O(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/logd/2-1n), ignoring log log n factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages94-100
Number of pages7
DOIs
StatePublished - 2008
Externally publishedYes
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

Keywords

  • Boxes
  • Data structures
  • Union of geometric objects

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A (slightly) faster algorithm for Klee's measure problem'. Together they form a unique fingerprint.

Cite this