Point-set triangulation

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (June 2021) (Learn how and when to remove this message)

A triangulation of a set of points ${\displaystyle {\mathcal {P}}}$ in the Euclidean space ${\displaystyle \mathbb {R} ^{d}}$ is a simplicial complex that covers the convex hull of ${\displaystyle {\mathcal {P}}}$, and whose vertices belong to ${\displaystyle {\mathcal {P}}}$.^[1] In the plane (when ${\displaystyle {\mathcal {P}}}$ is a set of points in ${\displaystyle \mathbb {R} ^{2}}$), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of ${\displaystyle {\mathcal {P}}}$ are vertices of its triangulations.^[2] In this case, a triangulation of a set of points ${\displaystyle {\mathcal {P}}}$ in the plane can alternatively be defined as a maximal set of non-crossing edges between points of ${\displaystyle {\mathcal {P}}}$. In the plane, triangulations are special cases of planar straight-line graphs.

A particularly interesting kind of triangulations are the Delaunay triangulations. They are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points ${\displaystyle {\mathcal {P}}}$ in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of ${\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 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.^[4]