Faster algorithms for largest empty rectangles and boxes

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

Abstract

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(n log2 n) for d = 2 (by Aggarwal and Suri [SoCG'87]) and near nd for d ≥ 3. We describe faster algorithms with running time O(n2O(log∗ n) log n) for d = 2, O(n2.5+o(1)) time for d = 3, and Oe(n(5d+2)/6) time 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)
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771849
DOIs
StatePublished - Jun 1 2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: Jun 7 2021Jun 11 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume189
ISSN (Print)1868-8969

Conference

Conference37th International Symposium on Computational Geometry, SoCG 2021
Country/TerritoryUnited States
CityVirtual, Buffalo
Period6/7/216/11/21

Keywords

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

ASJC Scopus subject areas

  • Software

Cite this