Faster Algorithms for Largest Empty Rectangles and Boxes

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(nlog2n) for d=2 (by Aggarwal and Suri [SoCG'87]) and near nd for d≥ 3. We describe faster algorithms with running time (i) O(n2O(log^*n)log n) for d=2, (ii) O(n2.5+o(1)) time for d=3, and (iii) widetildeO(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.