# 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 $O(n^{2}\log n)$ minimum area $O(n^{2})$ $O(n^{2}\log n)$ maximum $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 $O(n^{2})$ $O(n\log n)$ (using the Convex hull)
sum of NP-hard
(Minimum-weight triangulation)
minimum height $O(n^{2}\log n)$ maximum slope $O(n^{3})$ 