# Given a set of points X, locate the ball of maximum radius whose interior contains none of the points in X

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

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