2026-07-21T14:16:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13823 2024-03-06T10:52:48Z ddc:004 open_access

Faster Algorithms for Largest Empty Rectangles and Boxes Chan, Timothy M. Largest empty rectangle largest empty box Klee’s measure problem 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²n) for d = 2 (by Aggarwal and Suri [SoCG'87]) and near n^d for d ≥ 3. We describe faster algorithms with running time - O(n2^{O(log^*n)}log n) for d = 2, - O(n^{2.5+o(1)}) time for d = 3, and - Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.24 urn:nbn:de:0030-drops-138231 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.24 eng https://creativecommons.org/licenses/by/4.0/legalcode