Relocate points in Delaunay triangulation

Question

I just finished an implementation of the Delaunay's incremental flipping algorithm. This algorithm has a time complexity O(N log N).

The application of the algorithm is based on taking each point as an antenna of a telephone company. Using the Delaunay's algorithm, I have to triangulate the space with such points then generate a Voronoi diagram using the triangulation in which each Voronoi polygon represents the coverage of each antenna

Now, I must solve the following problem:

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.

I can not imagine how to solve this problem with an efficient algorithm. Delaunay's and Voronoi's algorithms are already implemented.

Thanks!

Answer 1

You can try Lloyd's algorithm. For each site compute the center of gravity and compare it with your old site. If the distance doesn't exceed the constant d relocate the site otherwise do nothing. Retriangulate the sites to smooth the mesh.