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 -