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. © 2001 Elsevier Science Ltd.