# Point-set triangulation

A triangulation of a set of points ${\mathcal {P}}$ in the Euclidean space $\mathbb {R} ^{d}$ is a simplicial complex that covers the convex hull of ${\mathcal {P}}$, and whose vertices belong to ${\mathcal {P}}$. In the plane (when ${\mathcal {P}}$ is a set of points in $\mathbb {R} ^{2}$), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of ${\mathcal {P}}$ are vertices of its triangulations. In this case, a triangulation of a set of points ${\mathcal {P}}$ in the plane can alternatively be defined as a maximal set of non-crossing edges between points of ${\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 ${\mathcal {P}}$ in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of ${\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).
Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is NP-complete.

## Regular triangulations

Some triangulations of a set of points ${\mathcal {P}}\subset \mathbb {R} ^{d}$ can be obtained by lifting the points of ${\mathcal {P}}$ into $\mathbb {R} ^{d+1}$ (which amounts to add a coordinate $x_{d+1}$ to each point of ${\mathcal {P}}$), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on $\mathbb {R} ^{d}$. The triangulations built this way are referred to as the regular triangulations of ${\mathcal {P}}$. When the points are lifted to the paraboloid of equation $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$, this construction results in the Delaunay triangulation of ${\mathcal {P}}$. 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 $d+2$ points of ${\mathcal {P}}$ lie in the same sphere.

## Combinatorics in the plane

Every triangulation of any set ${\mathcal {P}}$ of $n$ points in the plane has $2n-h-2$ triangles and $3n-h-3$ edges where $h$ is the number of points of ${\mathcal {P}}$ in the boundary of the convex hull of ${\mathcal {P}}$. This follows from a straightforward Euler characteristic argument.

## Algorithms to build triangulations in the plane

Triangle Splitting Algorithm : Find the convex hull of the point set ${\mathcal {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.
Incremental Algorithm : Sort the points of ${\mathcal {P}}$ according to x-coordinates. The first three points determine a triangle. Consider the next point $p$ in the ordered set and connect it with all previously considered points $\{p_{1},...,p_{k}\}$ which are visible to p. Continue this process of adding one point of ${\mathcal {P}}$ at a time until all of ${\mathcal {P}}$ has been processed.

## Time complexity of various algorithms

The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where $n$ is the number of points.
| | | minimize | maximize |
| minimum | angle | | $O(n\log n)$ (Delaunay triangulation) |
| maximum | angle | $O(n^{2}\log n)$ | |
| minimum | area | $O(n^{2})$ | $O(n^{2}\log n)$ |
| maximum | area | $O(n^{2}\log n)$ | |
| maximum | degree | NP-complete for degree of 7 | |
| maximum | eccentricity | $O(n^{3})$ | |
| minimum | edge length | $O(n\log n)$ (Closest pair of points problem) | NP-complete |
| maximum | edge length | $O(n^{2})$ | $O(n\log n)$ (using the Convex hull) |
| sum of | edge length | NP-hard (Minimum-weight triangulation) | |
| minimum | height | | $O(n^{2}\log n)$ |
| maximum | slope | $O(n^{3})$ | |