# Faster Algorithms for Largest Empty Rectangles and Boxes

arXiv: https://arxiv.org/abs/2103.08043 · HTML: https://mlsanity.com/paper/2103.08043/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2021.

## Built on by (most cited first, 2 of 2)

- [Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications](https://mlsanity.com/paper/2606.23858/) (2026)
- [Interval Certifications for Multilayered Perceptrons via Lattice Traversal](https://mlsanity.com/paper/2607.08773/) (2026)

## Abstract (arXiv)

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.