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 $\Theta(\frac{1}{n})$. We then use the fact that the maximum volume
is $\Omega(\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 $\Theta(\frac{1}{n})$. A faster $(1-\eps)$-approximation algorithm,
with a milder dependence on $d$ in the running time, is obtained in this case.

该研究给出了在超立方体中包含 n 个点的内部空置轴平行盒子的最大体积的上下界，并利用该界设计了一种高效的近似算法，该算法的运行时间与维度成对数增长，同时还给出了一个空置超立方体的最大体积估计。