On the largest empty axis-parallel box amidst $n$ points

Details On the largest empty axis-parallel box amidst $n$ points On the largest empty axis-parallel box amidst $n$ points

2009-09-16

arxiv.org/abs/0909.3127v2

Computer Science

Computational Geometry

19 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the largest empty axis-parallel box amidst $n$ points does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the largest empty axis-parallel box amidst $n$ points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the largest empty axis-parallel box amidst $n$ points will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389932