Empty axis-parallel boxes

Abstract

We show that, for every set of $n$ points in the $d$-dimensional unit cube, there is an empty axis-parallel box of volume at least $\Omega (d/n)$ as $n\to \infty$ and $d$ is fixed. In the opposite direction, we give a construction without an empty axis-parallel box of volume $O(d^2\log d/n)$. These improve on the previous best bounds of $\Omega (\log d/n)$ and $O(2^{7d}/n)$ respectively.

14 pages, derandomized algorithm, many minor changes