On the size of the largest empty box amidst a point set

Abstract The problem of finding the largest empty axis-parallel box amidst a point configuration is a classical problem in computational geometry. It is known that the volume of the largest empty box is of asymptotic order 1 ∕ n for n → ∞ and fixed dimension d . However, it is natural to assume that the volume of the largest empty box increases as d gets larger. In the present paper we prove that this actually is the case: for every set of n points in [ 0 , 1 ] d there exists an empty box of volume at least c d n − 1 , where c d → ∞ as d → ∞ . More precisely, c d is at least of order roughly log d .