Point-set triangulation

A triangulation of a set of points 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
 in the <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> 
 
 
 
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \mathbb {R} ^{d}}
 
 is a <a href="/facts/Simplicial_complex/fF2282CF">simplicial complex</a> that covers the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
, and whose vertices belong to 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
. In the <a href="/facts/Plane_(geometry)/tAUtRFcn">plane</a> (when 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
 is a set of points in 
 
 
 
 
 
 R
 
 
 2
 
 
 
 
 {\displaystyle \mathbb {R} ^{2}}
 
), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
 are vertices of its triangulations. In this case, a triangulation of a set of points 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
 in the plane can alternatively be defined as a maximal set of non-crossing edges between points of 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
. In the plane, triangulations are special cases of <a href="/facts/Planar_straight-line_graph/7MN0MycS">planar straight-line graphs</a>.
A particularly interesting kind of triangulations are the <a href="/facts/Delaunay_triangulation/6VRk7cS9">Delaunay triangulations</a>. They are the <a href="/facts/Dual_polytope/rkIHbmAf">geometric duals</a> of <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi diagrams</a>. The Delaunay triangulation of a set of points 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
 in the plane contains the <a href="/facts/Gabriel_graph/UYIRYo52">Gabriel graph</a>, the <a href="/facts/Nearest_neighbor_graph/6pdI9PlH">nearest neighbor graph</a> and the <a href="/facts/Minimal_spanning_tree/kgkGmY9s">minimal spanning tree</a> of 
 
 
 
 
 
 P
 
 
 
 
 {\displaystyle {\mathcal {P}}}
 
.
Triangulations have a number of applications, and there is an interest to find the "good" triangulations of a given point set under some criteria as, for instance <a href="/facts/Minimum-weight_triangulation/FoxpGHQb">minimum-weight triangulations</a>. Sometimes it is desirable to have a triangulation with special properties, e.g., in which all triangles have large angles (long and narrow ("splinter") triangles are avoided).
Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.

Point-set triangulation open-in-new

Point-set triangulation