将点插入有限的2D区域，并与现有点的距离最大

我在有限的二维空间区域内有一组二维点（比方说世界对齐的矩形，以便现在保持简单）。将一个新点插入到距离其最近的邻居有较大距离的集合中是一种非常有效的方法？将点插入有限的2D区域，并与现有点的距离最大

我可以慢慢建立Delaunay三角剖分并将搜索限制在最大的三角形上，但我希望有人有一个不同的（更好的）想法。

商誉，大卫

编辑：

忘了提，我需要做的这几千次，取前面所有的几点考虑每一次。我正在寻找一种算法，随着我的点数增长，不会减慢爬行速度。

那么你可以在空间的任何位置任意插入新的点，然后移动它，使它距离它最近的邻居可能的最大距离？请解释你如何插入一个新点。 – Jacob 2009-11-09 04:21:02

@Jacob，我还没有在任何地方插入点。我只想找一个地方插入一个，以便新插入的点和最近的邻居之间的距离相对较大。 – 2009-11-09 11:17:06

使用Bowyer-Watson或其他增量算法来维护Voronoi图。 Voronoi图的顶点是候选点，将所有候选点都保存在按距源点排序的优先级队列中。这应该是相当快的，并且是最优的（至少在每一步都是最优的）。

您是否在寻找速度更快，更不理想的东西？

2009-11-09 01:09:14

有人可能想要添加人们想要检查的细节作为候选点voronoi边与感兴趣区域的边界的交点。 – 2009-11-09 09:06:10

感谢Keith，实际上与我已经提到的方法相同（Delaunay三角剖分外圆中心点与Voronoi地图的顶点相同）。但至少我没有很酷的技巧。 – 2009-11-09 11:16:15

回答