Empty axis-parallel boxes

09/12/2020

∙

by   Boris Bukh, et al.

∙

0

∙

share

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 Ω(d/n) as n→∞ and d is fixed. In the opposite direction, we give a construction without an empty axis-parallel box of volume O(d^2log d/n). These improve on the previous best bounds of Ω(log d/n) and O(2^7d/n) respectively.