Point set triangulation
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. Template:Sfn It can alternatively be defined as a subdivision of the plane determined by a maximal set of noncrossing edges whose vertex set is P. Triangulations are special cases of planar straightline graphs.
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.
Triangulations have a number of applications, and there is an interest to find a "good" triangulation for a given point set under some criteria. One of them is a minimumweight triangulation. 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).^{[1]}
Given a set of edges that connect some pairs of the points, the problem to determine whether they contain a triangulation is NPcomplete .Template:Sfn
Triangulation and convex hull
A triangulation of the set S of ndimensional points in general position may be derived from the convex hull of a set of points S_{1} in the space of dimension larger by 1 which are the projections of the original point set onto the paraboloid surface . One has to construct the convex hull of the set S_{1} and project it back onto the space of S. If points are not in general position, additional effort is required to triangulate the nontetrahedral facets.
Complexity of the triangulation
Every triangulation of any set of n points has: triangles and edges where is the number of vertices of (the convex hull of P).^{[2]}
Algorithms
Triangle Splitting Algorithm : Find the convex hull of the point set P and triangulate this hull as a polygon. Choose an interior point and draw edges to the three vertices of the triangle that contains it. Continue this process until all interior points are exhausted.^{[3]}
Incremental Algorithm : Sort the points of P according to xcoordinates. The first three points determine a triangle. Consider the next point in the ordered set and connect it with all previously considered points which are visible to p. Continue this process of adding one point of P at a time until all of P has been processed.^{[4]}
Time complexity of various algorithms
The following is a table of time complexity results for different kinds of optimal point set triangulations.
minimize  maximize  

minimum  angle  (Delaunay triangulation)  
maximum  Template:Sfn Template:Sfn  
minimum  area  Template:Sfn  Template:Sfn 
maximum  Template:Sfn  
maximum  degree  NPcomplete for degree of 7 Template:Sfn 

maximum  eccentricity  Template:Sfn  
minimum  edge length  (Closest pair of points problem) 
NPcomplete Template:Sfn 
maximum  Template:Sfn  (using the Convex hull)  
sum of  NPhard (Minimumweight triangulation) 

minimum  height  Template:Sfn  
maximum  slope  Template:Sfn 
See also
Notes
 ↑ {{#invoke:citation/CS1citation CitationClass=book }}
 ↑ {{#invoke:citation/CS1citation CitationClass=citation }}.
 ↑ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
 ↑ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
References
 {{#invoke:citation/CS1citation
CitationClass=citation }}
 {{#invoke:Citation/CS1citation
CitationClass=journal }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=conference }}
 {{#invoke:citation/CS1citation
CitationClass=conference }}
 Template:Cite arXiv
 {{#invoke:citation/CS1citation
CitationClass=conference }}
 {{#invoke:citation/CS1citation
CitationClass=conference }}
de:Gitter (Geometrie)#Dreiecksgitter fr:Triangulation d'un ensemble de points