我刚刚完成了Delaunay增量翻转算法的实现 . 该算法具有时间复杂度 O(N log N) .
该算法的应用基于将每个点作为电话公司的天线 . 使用Delaunay算法，我必须使用这些点对空间进行三角测量，然后使用三角测量生成Voronoi图，其中每个Voronoi多边形代表每个天线的覆盖范围
现在，我必须解决以下问题：
对于每个给定点和常数d，重新定位平面中的所有点，而不超过距每个点的原始坐标的距离d，以便最大化Voronoi区域 .
我无法想象如何用一种有效的算法来解决这个问题 . Delaunay和Voronoi的算法已经实现 .
谢谢！
1 回答
你可以尝试Lloyd的算法 . 对于每个站点，计算重心并将其与旧站点进行比较 . 如果距离不超过常数d，则重新定位该站点，否则不执行任何操作 . 重新网格化网站以平滑网格 .