Faster Algorithms for Largest Empty Rectangles and Boxes

Research output: Contribution to journalArticlepeer-review


We revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst n given points in d dimensions. Previously, the best algorithms known have running time O(nlog 2n) for d= 2 (Aggarwal and Suri 1987) and near nd for d≥ 3. We describe faster algorithms with the following running times (where ε> 0 is an arbitrarily small constant and O~ hides polylogarithmic factors):n2O(log∗n)logn for d= 2 ,O(n2.5+ε) for d= 3 , andO~ (n(5d+2)/6) for any constant d≥ 4. To obtain the higher-dimensional result, we adapt and extend previous techniques for Klee’s measure problem to optimize certain objective functions over the complement of a union of orthants.

Original languageEnglish (US)
Pages (from-to)355-375
Number of pages21
JournalDiscrete and Computational Geometry
Issue number2
StatePublished - Sep 2023
Externally publishedYes


  • Klee’s measure problem
  • Largest empty box
  • Largest empty rectangle

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Faster Algorithms for Largest Empty Rectangles and Boxes'. Together they form a unique fingerprint.

Cite this