Delaunay Stable Zones

Martin Isenburg

This applet computes and depicts the Delaunay triangulation and the Voronoi diagram for vertices that can be interactively inserted, deleted or moved. For vertex insertion we implemented Guibas and Stolfi's incremental algorithm. For vertex deletion we used an approach from Terje Midtbø's thesis.

What makes this applet interesting is that the stable zone of each vertex can be highlighted. We define the stable zone of a vertex as the area around the vertex within it can be moved without retriangulating while preserving the Delaunay property. No edge swaps are necessary as long the moving vertex does leave its stable zone.

Use ctrl-click to select vertices that are NOT (*) on the convex hull. Pressing the Update-Stable-Zones button computes the stable zones of all selected vertices for the current triangulation. In order to see them the View-Stable-Zones checkbutton must be checked. Moving a vertex within its stable zone does not affect the shape of its own stable zone, but can change the shape of others.

The stable zone of a vertex is constrained by the circumcicles of triangles in the vertex's neigbourhood. With checking the View-Constraining-Circles checkbutton this should become more clear. It is better to have not more than one vertex selected for this option. The stable zone of a vertex is the difference of the intersection

of all black circles and the union

of all white circles.
The white circles are the circumcircles of triangles along the polygon surrounding the respective vertex, that do exist in the current Delaunay triangulation. The Delaunay property does not allow the vertex to lie inside one of those circumcircles, since otherwise the corresponding triangle would fail the Delaunay criterium. The black circles are the circumcircles of triangles along the polygon surrounding the respective vertex, that do not exist in the current Delaunay triangulation. The Delaunay property requires the vertex to lie inside all of those circumcircles, since otherwise the corresponding triangle would meet the Delaunay criterium (e.g. and exist in the current Delaunay triangulation).

(*) otherwise there is a nullpointer exception. There is also another little bug that results in wrong stable zones if one of the used constraining circles is a degenerated case that runs along the convex hull. Just stay in the center of the triangulation for stable zone stuff.