Delete point from Voronoi diagram efficiently

I have a point set and create a Delaunay triangulation and a Voronoi diagram. Then I would like to delete a point and calculate the Delaunay triangulation and Voronoi diagram again. It is easy to delete the point from the Delaunay trianglation: If I have a triangulation DT (DT = delaunayTriangulation(x,y)), I can delete a point using DT.Points(index,:) = [];. The question is how can I then create the new Voronoi diagram efficiently? I know that only the cells adjacent to the deleted point will change, so I would like to avoid computing the whole Voronoi diagram again.

Answer 1

[Ronit]

Hello Annika,

When you delete a point from a Delaunay triangulation, only the cells adjacent to the deleted point are affected in the Voronoi diagram. To efficiently update the Voronoi diagram without recomputing it entirely, you can recompute the triangulation for the affected region and recompute only the affected Voronoi cells based on the updated Delaunay triangulation. The new Voronoi edges will be formed by the perpendicular bisectors of the updated Delaunay edges.

% Identify affected points (neighbors of the point to be deleted)
affectedPoints = DT.vertexAttachments(index);

% Delete the point
DT.Points(index, :) = [];

% Update the Delaunay triangulation
% Recompute the triangulation for the affected region
% This step may require custom logic to identify and retriangulate the cavity

% Update the Voronoi diagram
% Recompute the Voronoi diagram only for the affected region
[vx, vy] = voronoi(DT.Points(:,1), DT.Points(:,2));

This approach minimizes the computational overhead by focusing on local changes, making it more efficient than recalculating the entire Voronoi diagram.

Please refer to the documentation of "vertexAttachments" for more details:

https://www.mathworks.com/help/matlab/ref/triangulation.vertexattachments.html

I hope it helps with your query!