Finding a point maximizing the minimal distance to a set of points 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.
 A: "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, 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].
