TY - JOUR
T1 - On the size of the largest empty box amidst a point set
AU - Aistleitner, Christoph
AU - Hinrichs, Aicke
AU - Rudolf, Daniel
PY - 2017
Y1 - 2017
N2 - 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 cdn−1, where cd → ∞ as d → ∞. More precisely, cd is at least of order roughly log d.
AB - 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 cdn−1, where cd → ∞ as d → ∞. More precisely, cd is at least of order roughly log d.
U2 - 10.1016/j.dam.2017.06.008
DO - 10.1016/j.dam.2017.06.008
M3 - Article
SN - 1872-6771
VL - 230
SP - 146
EP - 150
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -