Suppose $d$ is a metric space. Let $X$ be a finite set of points and let $B_R(x_0)$ be some ball such that $X \subset B_R(x_0)$. Find the maximum radius $r$ such that there exists a ball $B_r(p)$ whose centre is in $B_R(x_0)$ but whose interior contains no points in $X$.

Informally, where is the most isolated point in the vicinity of $X$? For example, if $X$ are three out of the four vertices on a square, then $p$ is the remaining vertex and $r$ is the width of the square. If $X$ is a finite representative sample of the Earth's coastlines, then $r = 1400\,\mathrm{NM}$ and $p$ is the oceanic pole of inaccessibility.

If it makes it easier, I'm thinking of the the Euclidean metric in $\mathbb{R}^2$ with the centre of the bounding ball in the centre of $X$.

I think the one-dimensional case is easy enough. Find the point at which the Hausdorff distance $d_H(X, X)$ occurs. The ball's radius will be half the Hausdorff distance and its centre will be to the right or left as required. For example, if $X = \{1, 2, 4\}$ then $p = 3$ and $r = 1$. However, this would locate the centre of the square rather than the fourth vertex in the example above.

(This is motivated by a 'real' problem of reverse geocoding addresses, so (1) ideally, I could derive an algorithmic solution, (2) the exact radius is not important, just a decent lower bound, and (3) questions of existence and uniqueness are not important to the problem -- I'm pretty sure yes and no are the answers though.)

  • 1
    $\begingroup$ This doesn't solve your problem, but since you mention the "pole of inaccessibility" it might contain some useful ideas. blog.mapbox.com/… $\endgroup$ Jan 17, 2019 at 7:57


You must log in to answer this question.

Browse other questions tagged .