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.

• without further restrictions on the solution, there is no finite maximum; commonly the task is to determine the largest empty hypersphere, whose center is inside the point set's convex hull; that is a standard task of computational geometry and is solved via generalistions of the Delaunay Triangulation - the generalisations exist for higher dimensions and/or metrics different from euclidean distance. – Manfred Weis May 13 '14 at 13:54
• That's exactly what I was thinking about (finding the largest hypersphere inside the convex hull). I'll look into the Delaunay Triangulation, thanks! – Wookai May 13 '14 at 14:22
• I found results for the 2D case, do you have any pointers to more recent works on the generalization to higher dimensions? – Wookai May 13 '14 at 14:59

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