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(nlog ²n) for d= 2 (Aggarwal and Suri 1987) and near n^d 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(n^2.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.