On the Largest Empty Axis-Parallel Box Amidst n Points

• DOI: 10.1007/s00453-012-9635-5
• Publication Date: 2012-03-06T16:00:29Z
• Authors: Adrian Dumitrescu; Minghui Jiang
• Keywords: Cube (algebra); Theory of computation; Unit cube

19 pages, 2 figures<br/>We give the first nontrivial upper and lower bounds on the maximum volume of an empty axis-parallel box inside an axis-parallel unit hypercube in $\RR^d$ containing $n$ points. For a fixed $d$, we show that the maximum volume is of the order $��(\frac{1}{n})$. We then use the fact that the maximum volume is $��(\frac{1}{n})$ in our design of the first efficient $(1-\eps)$-approximation algorithm for the following problem: Given an axis-parallel $d$-dimensional box $R$ in $\RR^d$ containing $n$ points, compute a maximum-volume empty axis-parallel $d$-dimensional box contained in $R$. The running time of our algorithm is nearly linear in $n$, for small $d$, and increases only by an $O(\log{n})$ factor when one goes up one dimension. No previous efficient exact or approximation algorithms were known for this problem for $d \geq 4$. As the problem has been recently shown to be NP-hard in arbitrary high dimensions (i.e., when $d$ is part of the input), the existence of efficient exact algorithms is unlikely. We also obtain tight estimates on the maximum volume of an empty axis-parallel hypercube inside an axis-parallel unit hypercube in $\RR^d$ containing $n$ points. For a fixed $d$, this maximum volume is of the same order order $��(\frac{1}{n})$. A faster $(1-\eps)$-approximation algorithm, with a milder dependence on $d$ in the running time, is obtained in this case.<br/>