如何从许多点中找到最远的x，y坐标？

Question

我在平面上有一组随机点，我想在最“稀疏”的位置放置另一个点。

例如，如果在0

# 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()

我应在该平面上的哪个位置放置新点，以使新点与其他点之间的距离最远？请注意，我想最大化到另一个点的最小距离，而不是最大化到所有其他点的平均距离（感谢user985366's comment）。

“ How can I find the farthest point from a set of existing points?”是我至少可以找到的那个，但是我不确定页面是否可以直接解决我的情况（实际上，链接的情况看起来比我的情况复杂）。

[edit]顺便说一下，在这种情况下，我注意到一般约束全局优化可以找到可能的解决方案（如果我在每个角处添加一个点）[4.01，5.48]，但我认为如果有的话，它是行不通的还有很多，比如说〜10000点。

Answer 1

您的问题可以通过计算点集的Voronoi diagram来解决。这是将平面划分为多个区域，以使原始集合中的每个点都有一个区域，并且在该区域内，对应点比该集合中的其他点更近。

这些区域的边界是直线，因此该线上的任何点都与对应于在该边界处会合的区域的两个点等距。因此，多个边界相交的顶点与原始集合至少等距三个点。

[平面中最稀疏的点是Voronoi图中的一个顶点，或者是Voronoi图中的一条边与平面的边界或平面的一个角的交点。 Voronoi图可以通过standard algorithms在O（n log n）时间中计算；此后，可以在线性时间内找到最稀疏的点，因为您知道每个顶点/边与哪个Voronoi区域相邻，并因此知道原始集合中的哪个点可以测量到的距离。]

Answer 2

您的问题可以通过计算点集的Voronoi diagram来解决。这是将平面划分为多个区域，以使原始集合中的每个点都有一个区域，并且在该区域内，对应点比该集合中的其他点更近。

这些区域的边界是直线，因此该线上的任何点都与对应于在该边界处会合的区域的两个点等距。因此，多个边界相交的顶点与原始集合至少等距三个点。

[平面中最稀疏的点是Voronoi图中的一个顶点，或者是Voronoi图中的一条边与平面的边界或平面的一个角的交点。 Voronoi图可以通过standard algorithms在O（n log n）时间中计算得出；此后，可以在线性时间内找到最稀疏的点，因为您知道每个顶点/边与哪个Voronoi区域相邻，因此知道原始集合中的哪个点可以测量到的距离。]