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?