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... View More