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?



finding the most-isolated point in a high-dimensional cube
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](http://planning.cs.uiuc.edu/node203.html).
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](http://www.sciencedirect.com/science/article/pii/0895717796000362))
> 
> 
> 


**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](http://www.cs.uwm.edu/faculty/ad/tau2.pdf)):



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


