Point-set triangulation

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]

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

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

Triangle Splitting Algorithm : Find the convex hull of the point set ${\displaystyle {\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.^[6]

Incremental Algorithm : Sort the points of ${\displaystyle {\mathcal {P}}}$ according to x-coordinates. The first three points determine a triangle. Consider the next point ${\displaystyle p}$ in the ordered set and connect it with all previously considered points ${\displaystyle \{p_{1},...,p_{k}\}}$ which are visible to p. Continue this process of adding one point of ${\displaystyle {\mathcal {P}}}$ at a time until all of ${\displaystyle {\mathcal {P}}}$ has been processed.^[7]

The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where ${\displaystyle n}$ is the number of points.

		minimize	maximize
minimum	angle		${\displaystyle O(n\log n)}$ (Delaunay triangulation)
maximum		${\displaystyle O(n^{2}\log n)}$ [8] [9]
minimum	area	${\displaystyle O(n^{2})}$ [10]	${\displaystyle O(n^{2}\log n)}$ [11]
maximum		${\displaystyle O(n^{2}\log n)}$ [11]
maximum	degree	NP-complete for degree of 7 [12]
maximum	eccentricity	${\displaystyle O(n^{3})}$ [9]
minimum	edge length	${\displaystyle O(n\log n)}$ (Closest pair of points problem)	NP-complete [13]
maximum		${\displaystyle O(n^{2})}$ [14]	${\displaystyle O(n\log n)}$ (using the Convex hull)
sum of		NP-hard (Minimum-weight triangulation)
minimum	height		${\displaystyle O(n^{2}\log n)}$ [9]
maximum	slope	${\displaystyle O(n^{3})}$ [9]

• Mesh generation
• Polygon triangulation