Point set triangulation

From Wikipedia, the free encyclopedia

A triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. Triangulations are special cases of planar straight-line graphs.

Sometimes it is desirable to have a triangulation with special properties, e.g., in which the triangles each have large angles ("splinter" triangles are avoided).

There are special triangulations like the Delaunay triangulation which is the geometric dual of the Voronoi diagram. Subsets of the Delaunay triangulation are the Gabriel graph, nearest neighbor graph and the minimal spanning tree.

Triangulation of the set of points may be a subproblem of the convex hull question in the space of dimension larger by 1.