如何找到距离很多点最远的x,y坐标？
How to find the farthest x, y coordinates from many points?
我在一个平面上有一组随机点，我想在最"sparse"的位置再放一个点。
例如，如果有一些点在 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()
我应该在这个平面的什么地方放置一个新点，以便新点与其他点最远？请注意，我想最大化到另一个点的最小距离，而不是最大化到所有其他点的平均距离（感谢 ）。
"How can I find the farthest point from a set of existing points?" 是至少我能找到的，但我不确定该页面是否直接解决了我的情况（实际上链接的情况看起来比我的情况更复杂）。
[edit] 顺便说一句，我注意到一般约束全局优化可以找到一个可能的解决方案（如果我在每个角落添加一个点）[4.01, 5.48] 在这种情况下，但我认为它不会如果还有更多，请工作，比如 ~10000 点。
您的问题可以通过计算点集的 Voronoi diagram 来解决。这是将平面划分为区域，使得原始集合中的每个点都有一个区域，并且在该区域内，对应的点比集合中的其他点更近。
这些区域的边界是直线，使得该线上的任何点与对应于在该边界相交的区域的两点等距。因此，多个边界相交的顶点与原始集合中的至少三个点等距。
平面上最稀疏的点要么是Voronoi图中的一个顶点，要么是Voronoi图中的一条边与平面边界的交点，要么是平面的一个角。 Voronoi 图可以在 O(n log n) 时间内通过 standard algorithms 计算；在此之后，可以在线性时间内找到最稀疏的点，因为你知道每个 vertex/edge 与哪些 Voronoi 区域相邻，因此可以从原始集合中的哪个点测量距离。
我在一个平面上有一组随机点，我想在最"sparse"的位置再放一个点。
例如，如果有一些点在 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()
我应该在这个平面的什么地方放置一个新点，以便新点与其他点最远？请注意，我想最大化到另一个点的最小距离，而不是最大化到所有其他点的平均距离（感谢
"How can I find the farthest point from a set of existing points?" 是至少我能找到的，但我不确定该页面是否直接解决了我的情况（实际上链接的情况看起来比我的情况更复杂）。
[edit] 顺便说一句，我注意到一般约束全局优化可以找到一个可能的解决方案（如果我在每个角落添加一个点）[4.01, 5.48] 在这种情况下，但我认为它不会如果还有更多，请工作，比如 ~10000 点。
您的问题可以通过计算点集的 Voronoi diagram 来解决。这是将平面划分为区域，使得原始集合中的每个点都有一个区域，并且在该区域内，对应的点比集合中的其他点更近。
这些区域的边界是直线，使得该线上的任何点与对应于在该边界相交的区域的两点等距。因此，多个边界相交的顶点与原始集合中的至少三个点等距。
平面上最稀疏的点要么是Voronoi图中的一个顶点，要么是Voronoi图中的一条边与平面边界的交点，要么是平面的一个角。 Voronoi 图可以在 O(n log n) 时间内通过 standard algorithms 计算；在此之后，可以在线性时间内找到最稀疏的点，因为你知道每个 vertex/edge 与哪些 Voronoi 区域相邻，因此可以从原始集合中的哪个点测量距离。