12
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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, 2012 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, 2012 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, 2012 at 2:12

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2012 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, 2012 at 1:31
4
$\begingroup$

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)$.

Improve this answer
$\endgroup$
0
$\begingroup$

http://scicomp.stackexchange.com

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.