文章基本信息

标题：Faster Algorithms for Largest Empty Rectangles and Boxes
本地全文：下载
作者：Chan, Timothy M.
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：189
页码：24:1-24:15
DOI：10.4230/LIPIcs.SoCG.2021.24
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 - OÌf(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.
关键词：Largest empty rectangle; largest empty box; Kleeâs measure problem