Voronoi-Delaunay duality and Delaunay meshes
Ramsay Dyer, Hao Ran Zhang, Torsten Bert Möller · 2007
In this paper, we are concerned with Delaunay triangulations of the vertex set of a piecewise flat (pwf) surface. We first propose the notion of well-formed Voronoi diagrams and establish a precise dual relationship between them and proper Delaunay triangulations on pwf surfaces. Then we provide an algorithm which, given any input manifold triangle mesh, constructs a Delaunay mesh: a manifold triangle mesh whose edges form an intrinsic Delaunay triangulation of its vertex set. Rather than relying on a geodesic Delaunay triangulation on the input mesh, our algorithm swaps the physical mesh edges based on the locally Delaunay criterion. We prove that when a physical edge that is not locally Delaunay is swapped, the surface area of the mesh is reduced. In order to ensure a proper Delaunay triangulation, some new vertices may need to be introduced, leading to a refinement scheme, and we detail the cases involved.