algorithm - 在 Delaunay 三角剖分中重新定位点

Question

我刚刚完成了 Delaunay 增量翻转算法的实现。该算法的时间复杂度为 O(N log N)。

该算法的应用是基于将每个点作为电话公司的天线。使用 Delaunay 算法，我必须用这些点对空间进行三角剖分，然后使用三角剖分生成 Voronoi 图，其中每个 Voronoi 多边形代表每个天线的覆盖范围

现在，我必须解决以下问题:

For each given point, and a constant d, relocate all the points in the plane, without exceeding the distance d from the original coordinates of each point, so that the Voronoi regions are maximized.

我无法想象如何用高效的算法来解决这个问题。 Delaunay 和 Voronoi 的算法已经实现。

谢谢!

Answer 1

您可以尝试 Lloyd 算法。为每个站点计算重心并将其与您的旧站点进行比较。如果距离不超过常量 d，则重新定位站点，否则什么都不做。重新对站点进行三角测量以平滑网格。