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

Question

我有一组一个有限的空间2D区域内的2D点（比方说，一个世界对齐矩形让事情变得简单现在）。什么是插入一个新的点到具有其新最近的邻国比较大的距离的设定一个非常有效的方式？

我可以慢慢建立一个三角网和限制我的搜索仅最大的三角形，但我希望有人有不同的（更好的）想法。

好感， 大卫

---

编辑：

忘了提，我需要做的这几千次，取前面所有的几点考虑每一次。我在寻找一种算法，为我点集增长不减速到爬行。

Answer 1

使用鲍耶沃森或其它增量算法，以保持Voronoi图。 Voronoi图的顶点是候选点，把所有的候选点中按距离排序的源点的优先级队列。这应该是相当快，并且最佳的（至少，在每一步最优的）。

是你寻找的东西更快，更优化？