Given a set of of $N$ points $\{\mathbf x\_i \in \mathcal{S}^d\}\_{i = 1, \ldots, N}$, where $\mathcal{S}$ is a set of possible values, how can I find the point $\mathbf x^\*$ that maximizes the minimum distance to all data points?


In other words, I want to solve:


$\max\_{\mathbf x^\* \in \mathcal{S}^d} \min\_{i = 1, \ldots, N} (\mathbf x^\* - \mathbf x\_i)^2$


The distance should be the euclidian distance, but relaxation to L1 would work, too. Exhaustive search is not feasible, as $d=75$, $N = 3000$ and $|\mathcal{S}| = 4$ in my application.



Finding a point maximizing the minimal distance to a set of points
"Do you have any pointers to more recent works on the generalization to higher dimensions?"



> 
> Xie, Yulai, Jack Snoeyink, and Jinhui Xu. "Efficient algorithm for approximating maximum inscribed sphere in high-dimensional polytope." *Proceedings 22nd Symposium on Computational Geometry*. [ACM link](http://dl.acm.org/citation.cfm?id=1137861), 2006.
> 
> 
> 


**Abstract**.
In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a $(1−ε)$-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by $n$ $d$-dimensional halfspaces, an interior point $O$ of $P$, and a constant $ε>0$, our algorithm computes in $O(nd/ε^3)$ time a sphere inside $P$ with a radius no less than $(1−ε)$Ropt, where Ropt is the radius of a maximum inscribed sphere of $P$. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].


