Definitions (of several geometric terms)


A Delaunay triangulation of a point set is a triangulation of the point set with the property that no point in the point set falls in the interior of the circumcircle (circle that passes through all three vertices) of any triangle in the triangulation.


A Voronoï diagram of a point set is a subdivision of the plane into polygonal regions (some of which may be infinite), where each region is the set of points in the plane that are closer to some input point than to any other input point. (The Voronoï diagram is the geometric dual of the Delaunay triangulation.)


A Planar Straight Line Graph (PSLG) is a collection of points and segments. Segments are edges whose endpoints are points in the PSLG, and whose presence in any mesh generated from the PSLG is enforced.


A constrained Delaunay triangulation of a PSLG is similar to a Delaunay triangulation, but each PSLG segment is present as a single edge in the triangulation. (A constrained Delaunay triangulation is not truly a Delaunay triangulation.)


A conforming Delaunay triangulation of a PSLG is a true Delaunay triangulation in which each PSLG segment may have been subdivided into several edges by the insertion of additional points, called Steiner points. Steiner points are necessary to allow the segments to exist in the mesh while maintaining the Delaunay property. Steiner points are also inserted to meet constraints on the minimum angle and maximum triangle area.


Return to Triangle home page.
jrs@cs.cmu.edu