6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Manfred Weis May 13 '14 at 13:54
  • $\begingroup$ That's exactly what I was thinking about (finding the largest hypersphere inside the convex hull). I'll look into the Delaunay Triangulation, thanks! $\endgroup$ – Wookai May 13 '14 at 14:22
  • $\begingroup$ I found results for the 2D case, do you have any pointers to more recent works on the generalization to higher dimensions? $\endgroup$ – Wookai May 13 '14 at 14:59
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.