如何定位定义的二维区域内最稀疏的点？

Question

问题的核心是通过算法确定点 E 的坐标，使有界 2D 空间中与最近的其他点的距离最大化。

例如，在由坐标

[(0, 0), (1, 1)]

定义的空间中，包含如下所示的点 A₁、B₁、C₁ 和 D₁，目标“最稀疏”点是 E₁

(0.5, 0.5)

:

换句话说，目标点E，我指的是这个“最稀疏”点（密度最小的点）的坐标，而不是从现有的点集中选择它。

那么，您能建议一种有效的算法或方法来解决这个问题吗？

Answer 1

您可以使用同一维基百科页面上列出的算法之一来制作 Voronoi 图。

然后考虑以下所有顶点：

• 边界矩形的四个角
• Voronoi 图与边界矩形的交点
• 位于边界矩形内的 Voronoi 图的顶点

检查这些点中哪一个是“最稀疏”的。