8
$\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.

Improve this question
$\endgroup$
3
  • $\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
    Commented May 13, 2014 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
    Commented May 13, 2014 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
    Commented May 13, 2014 at 14:59

1 Answer 1

Reset to default
4
$\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].

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .