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

Research output: Contribution to journalArticle

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/ 2logn) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time nd/ 22 O( logn), 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(nd/ 2/logd/ 2-1n), ignoring loglogn factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.

Original languageEnglish (US)
Pages (from-to)243-250
Number of pages8
JournalComputational Geometry: Theory and Applications
Volume43
Issue number3
DOIs
StatePublished - Apr 1 2010
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • 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