TY - GEN
T1 - Faster algorithms for largest empty rectangles and boxes
AU - Chan, Timothy M.
N1 - Publisher Copyright:
© Timothy M. Chan; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).
PY - 2021/6/1
Y1 - 2021/6/1
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(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.
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(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.
KW - Klee's measure problem
KW - Largest empty box
KW - Largest empty rectangle
UR - http://www.scopus.com/inward/record.url?scp=85108220861&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108220861&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2021.24
DO - 10.4230/LIPIcs.SoCG.2021.24
M3 - Conference contribution
AN - SCOPUS:85108220861
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Computational Geometry, SoCG 2021
A2 - Buchin, Kevin
A2 - de Verdiere, Eric Colin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th International Symposium on Computational Geometry, SoCG 2021
Y2 - 7 June 2021 through 11 June 2021
ER -