如何找到距离很多点最远的x,y坐标？

Question

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

例如，如果 0 < x < 10 和 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()

我应该在这个平面上的哪里放置一个新点，以便该新点距离其他点最远？请注意，我想最大化到另一个点的最小距离，但不是最大化到所有其他点的平均距离（感谢user985366 的评论）。

“如何找到距离一组现有点最远的点？ ”是至少我能找到的，但我不确定该页面是否直接解决了我的情况（实际上链接的案例看起来比我的情况更复杂） 。

[编辑]顺便说一句，我注意到一般约束全局优化可以找到一个可能的解决方案（如果我在每个角添加一个点）[4.01，5.48]在这种情况下，但我认为如果有一个更多，比如说~10000点。

Answer 1

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

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

平面中最稀疏的点要么是 Voronoi 图中的顶点，要么是 Voronoi 图中的一条边与平面边界的交点，或者是平面的角之一。Voronoi 图可以通过标准算法在 O(n log n) 时间内计算出来；之后，可以在线性时间内找到最稀疏的点，因为您知道每个顶点/边与哪些 Voronoi 区域相邻，因此知道要测量到原始集合中的哪个点的距离。