Delaunay and Voronoi tessellations and minimal simple cycles in triangular region and regular-3 undirected planar graphs
Linear time algorithms are presented which generate the Voronoi tessellation from a Delaunay tessellation and vice versa when the tessellations of convex polygons and triangles are stored as edge-adjacent undirected graphs. These two geometric algorithms lead naturally to two further linear and quadratic graph algorithms for determining the minimal simple cycles or regions in both triangular and regular-3 undirected planar graphs.
delaunay and voronoi tessellations graph algorithms computational geometry