Delaunay Meshes


Ramsay Dyer, Hao Zhang, and Torsten Moeller

Just as the Delaunay triangulation has proven itself as an invaluable concept for meshing planar domains, Delaunay structures are often invoked when meshing surfaces in three dimensional space. However, in the latter context there are a few distinct ways to extend the concept of the Delaunay triangulation. The traditional structure is called the restricted Delaunay triangulation. It is the dual of the restricted Voronoi diagram: the 3D Voronoi diagram restricted to the surface to be approximated by the mesh. Another possibility is to use the dual of the Voronoi diagram defined by the intrinsic (geodesic) distance measure on the surface. Recently a new Delaunay mesh structure has emerged. It is a triangle mesh that is a Delaunay triangulation of its vertices with respect to its own intrinsic metric. It is attractive because it does not need the original surface for its definition. However, this also introduces difficulties when making approximation accuracy claims. We are studying the differences and similarites between these three structures, with a focus on illuminating the properties of the latter.