finding the most-isolated point in a high-dimensional cube 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?
 A: 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.
A: 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)$.
A: http://scicomp.stackexchange.com
