I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find $\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} \|\omega-x_i\|_2$.

The problem isn't convex, but I'm hoping there's an efficient way to solve it, perhaps in quadratic time by evaluating midpoints. (Just a thought...it's not clear to me how to do this unless $d=1$.)

I've tried constructing the (bounded) Voronoi diagram. I thought that if I could construct the Voronoi diagram, then I could just evaluate the objective function at each of its vertices, and return the maximum. But generating a Voronoi diagram doesn't seem tractable for $d>8$, at least with the qhull library. Might there be some fast way to generate just the positive Veronoi poles, without generating the whole Voronoi diagram?

I've also tried approximating a solution to a related problem using a branch-and-bound algorithm, but with so many dimensions, branch-and-bound isn't really better than just evaluating my objective function at a bunch of randomly selected points -- at least wrt finding a good lower bound. (I don't need an upper bound.)

Any other approaches to solving it, or to proving that it can't be solved efficiently?

  • 3
    $\begingroup$ If you have a notion of how the points are scattered, you might approximate your value by a form of judicious guessing. In high dimensions though, balls are more "spikey": you might find brute forcing an evaluation from each of the 2^25 corners to be a highly successful estimate. Gerhard "Spikey Is A Technical Term" Paseman, 2012.06.02 $\endgroup$ – Gerhard Paseman Jun 2 '12 at 21:48
  • $\begingroup$ Garhard -- I like the idea of evaluating all of the corners, and I can imagine this yielding a useful lower bound, but I'd need some way to justify ignoring the interior. Can you give any more intuition about the sense in which high-dimensional balls are spikey? Thanks! $\endgroup$ – Jeff Jun 3 '12 at 22:01
  • $\begingroup$ Here you go: divide each edge in half. Of the over 32 million sub chambers of half size, at most 1000 of them will contain a point. Someone else should do the math, but the distance squared will probably be around 3 as a lower bound. I am unsure, but this might be implicit in Joseph's suggestions. Gerhard "Not Spikey, But Hopefully Revealing" Paseman, 2012.06.03 $\endgroup$ – Gerhard Paseman Jun 4 '12 at 2:12

I believe you are looking for the radius of a largest empty ball among your point set, a quantity which goes under the name of dispersion. This plays a role in robotics algorithms, e.g., LaValle's book. Here is a survey which might lead to other relevant references:

G. Rote , R.F. Tichy, "Quasi-Monte-Carlo methods and the dispersion of point sequences," Mathematical and Computer Modelling, 1996. (link)

Addendum. In repsonse to Jeff's query, let me recommend another direction, a very recent (2012) paper by Dumitrescu and Jiang, "On the largest empty axis-parallel box amidst $n$ points" (PDF download):

Our algorithm finds an empty axis-aligned box [in $\mathbb{R}^d$] whose volume is at least $(1 − \epsilon)$ of the maximum in [...] time"

where I have elided a complicated complexity expression. This paper's 28 citations may prove useful to you.

  • $\begingroup$ It sounds like "dispersion" is exactly what I'm trying to compute! The article and its references make use of dispersion, to establish bounds for function approximation, or to select good point sets, but they don't seem to address computing dispersion on a pre-specified set of points. The latter is what I'm trying to do. Are there any known algorithms for that? Thanks much. $\endgroup$ – Jeff Jun 3 '12 at 21:52
  • $\begingroup$ This is great! I was originally asking about $L_2$ balls, but $L_\infty$ balls work too. Many thanks. $\endgroup$ – Jeff Jun 4 '12 at 1:31

A slight improvement on testing random points is to use a hill-climbing method. After you pick a random point, move it to increase the minimum distance until you hit a $(d-1)$-face of the Voronoi cell, then move within that hyperplane until you hit a $(d-2)$-face, etc. with special cases for hitting the boundary of the cube. It looks like the time it takes to move each starting point to a corner of a Voronoi cell should be at most $O(d^2 n)$.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.