How to find the farthest x, y coordinates from many points?

Question

I have a set of random points in a plane and I want to put another point at the most "sparse" position.

For example, if there are some points in 0 < x < 10 and 0 < y < 10:

# this python snippet just generates the plot blow.
import matplotlib.pyplot as plt

# there are actually a lot more, ~10000 points.
xs = [8.36, 1.14, 0.93, 8.55, 7.49, 6.55, 5.13, 8.49, 0.15, 3.48]
ys = [0.65, 6.32, 2.04, 0.51, 4.5, 7.05, 1.07, 5.23, 0.66, 2.54]
plt.xlim([0, 10])
plt.ylim([0, 10])
plt.plot(xs, ys, 'o')
plt.show()

Where should I put a new point in this plane so that the new point becomes the most distant from the others? Please note that I want to maximise the minimum distance to another point, but not to maximise the average distance to all other points (Thanks to user985366's comment).

"How can I find the farthest point from a set of existing points?" is the one at least I could find, but I'm not sure if the page directly solves my situation (actually the linked case looks more complicated than my case).

[edit] By the way, I noticed that general constrained global optimization can find a possible solution (if I add a point at each corner) [4.01, 5.48] in this case, but I think it doesn't work if there are a lot more, say ~10000 points.

Answer 1

Your problem can be solved by computing the Voronoi diagram of the set of points. This is a division of the plane into regions such that there is one region per point in the original set, and within that region, the corresponding point is closer than other points from the set.

The boundaries of these regions are straight lines such that any point on that line is equidistant from the two points corresponding to the regions which meet at that boundary. The vertices where multiple boundaries meet are therefore equidistant to at least three points from the original set.

The sparsest point in the plane is either a vertex in the Voronoi diagram, or the intersection of an edge in the Voronoi diagram with the boundary of the plane, or one of the corners of the plane. The Voronoi diagram can be computed by standard algorithms in O(n log n) time; after this, the sparsest point can then be found in linear time, since you know which Voronoi regions each vertex/edge is adjacent to, and hence which point from the original set to measure the distance to.