TY - JOUR

T1 - Faster Algorithms for Largest Empty Rectangles and Boxes

AU - Chan, Timothy M.

N1 - Funding Information:
This work was financially supported by National Natural Science Foundation of China (22269003 and 21902064), Guangdong province innovation and strong school project (2020ZDZX2004), The central government guides local science and technology development funds ([2022]4053), and Project of Guizhou Provincial Department of Education ([2022]056).
Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/9

Y1 - 2023/9

N2 - 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.

AB - 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.

KW - Klee’s measure problem

KW - Largest empty box

KW - Largest empty rectangle

UR - http://www.scopus.com/inward/record.url?scp=85146986764&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85146986764&partnerID=8YFLogxK

U2 - 10.1007/s00454-022-00473-x

DO - 10.1007/s00454-022-00473-x

M3 - Article

AN - SCOPUS:85146986764

SN - 0179-5376

VL - 70

SP - 355

EP - 375

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -