## Abstract

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 ^{2}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^{(}^{5}^{d}^{+}^{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.

Original language | English (US) |
---|---|

Pages (from-to) | 355-375 |

Number of pages | 21 |

Journal | Discrete and Computational Geometry |

Volume | 70 |

Issue number | 2 |

DOIs | |

State | Published - Sep 2023 |

Externally published | Yes |

## Keywords

- Klee’s measure problem
- Largest empty box
- Largest empty rectangle

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics