Point-set triangulation

is a simplicial complex that covers the convex hull of

), triangulations are made up of triangles, together with their edges and vertices.

[2] In this case, a triangulation of a set of points

in the plane can alternatively be defined as a maximal set of non-crossing edges between points of

In the plane, triangulations are special cases of planar straight-line graphs.

They are the geometric duals of Voronoi diagrams.

The Delaunay triangulation of a set of points

in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of

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 minimum-weight triangulations.

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).

[3] Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is NP-complete.

(which amounts to add a coordinate

), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on

When the points are lifted to the paraboloid of equation

, this construction results in the Delaunay triangulation of

Note that, in order for this construction to provide a triangulation, the lower convex hull of the lifted set of points needs to be simplicial.

In the case of Delaunay triangulations, this amounts to require that no

This follows from a straightforward Euler characteristic argument.

[5] Triangle Splitting Algorithm : Find the convex hull of the point set

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.

[6] Incremental Algorithm : Sort the points of

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

[7] The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where