我刚刚完成了delaunay增量翻转算法的一个实现。该算法具有时间复杂度O(N log N)。
该算法的应用是以每个点作为电话公司的天线使用Delaunay算法，我必须用这些点对空间进行三角剖分，然后使用三角剖分生成Voronoi图，其中每个Voronoi多边形表示每个天线的覆盖范围
现在，我必须解决以下问题：
对于每个给定的点，和常数d，重新定位平面中的所有点，而不超过每个点的原始坐标的距离d，从而使Voronoi区域最大化。
我无法想象如何用一个有效的算法来解决这个问题。Delaunay和Voronoi的算法已经实现。
谢谢！
最佳答案
你可以试试劳埃德的算法对于每个站点，计算重心并将其与旧站点进行比较如果距离不超过固定的重新安置地点，否则什么也不做。重新调整位置使网格平滑。