CODEWITHSUNDEEP
algorithmoptimizationcomputational-geometrydelaunayvoronoi
Valentina Ramirez
Valentina Ramirez

Reputation: 113

Relocate points in Delaunay triangulation

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!

Upvotes: 0

Views: 217

Answers (1)

Cybercartel
Cybercartel

Reputation: 12592

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.

Upvotes: 2

Related Questions