Triangulation (geometry)
A triangulation in geometry is a subdivision of a geometric object into triangles, or more generally into simplices, whose intersections satisfy prescribed compatibility conditions. For a planar region, the triangles cover the region without overlapping interiors, and the intersection of any two triangles is either empty or consists of a shared vertex or a complete shared edge. The term also denotes the resulting simplicial complex, rather than only the act of forming it.
Triangulation connects Euclidean geometry, combinatorial topology, and computational geometry. Its elementary form concerns the dissection of a polygon by nonintersecting diagonals, while its broader forms include triangulations of finite point sets, curved surfaces, manifolds, and higher-dimensional polytopes. Although these settings share a common combinatorial structure, they differ in their permitted vertices and in the geometric object required to equal the union of the simplices.
Polygon triangulations
Let (P) be a simple polygon with (n) vertices. A triangulation of (P) using no additional vertices is a collection of triangles whose union is (P), with every triangle vertex belonging to the vertex set of (P). The interior edges are diagonals of the polygon, and no two such diagonals cross.
Every simple polygon admits a triangulation. This existence result follows from the two ears theorem, which states that every simple polygon with more than three vertices has at least two nonoverlapping ears. An ear is a triangle formed by three consecutive polygon vertices whose interior lies inside the polygon. Removing one ear produces a polygon with one fewer vertex, allowing an inductive decomposition.
Every triangulation of an (n)-vertex simple polygon contains exactly
[ n-2 ]
triangles and
[ n-3 ]
interior diagonals. These quantities do not depend on the shape of the polygon or on the selected triangulation. They follow from counting incidences between triangles and edges, together with Euler's formula for a planar graph embedded in a disk.
For a convex polygon, every diagonal lies inside the polygon, so any maximal set of pairwise noncrossing diagonals is a triangulation. The number of distinct triangulations of a convex polygon with (n) vertices is the Catalan number
[ C_{n-2} = \frac{1}{n-1}\binom{2n-4}{n-2}. ]
This formula reflects a recursive decomposition: the triangle incident to a fixed boundary edge separates the remaining vertices into two smaller convex polygons. Summing over the possible third vertices produces the Catalan recurrence.
Polygon triangulations also carry a natural graph structure. Two triangulations are adjacent when one can be obtained from the other by replacing the diagonal of a convex quadrilateral with its other diagonal. This operation is an edge flip. The graph whose vertices represent triangulations and whose edges represent flips is connected. In the convex case, it is the one-skeleton of the associahedron.
Triangulations of planar point sets
For a finite point set (S\subset\mathbb{R}^2), a triangulation is a maximal planar straight-line graph having (S) as its vertex set. Its bounded faces are triangles, and its unbounded face has the boundary of the convex hull of (S). Maximality is equivalent to the absence of any additional noncrossing straight edge between two points of (S).
If (S) contains (n) points and exactly (h) of them lie on the convex-hull boundary, every triangulation has
[ 2n-h-2 ]
bounded triangular faces and
[ 3n-h-3 ]
edges. These identities again follow from Euler's formula and from counting each interior edge twice among the triangular faces while counting each hull edge once.
Collinearities create faces that require additional care. When three or more input points lie on the same supporting line, the definition normally treats intermediate collinear points as vertices of the corresponding subdivided boundary or edge. A point set in general position has no three collinear points, which removes this degeneracy but does not determine a unique triangulation.
The combinatorial type of a triangulation records vertex incidences without retaining exact lengths or angles. Two geometric point sets may therefore support equivalent abstract triangulations even when their coordinates differ. Conversely, not every abstract planar triangulation can be realized with an arbitrarily prescribed set of point positions, because the straight-line embedding imposes orientation and nonintersection constraints.
Diagonal exchanges and connectivity
An interior edge shared by two triangles is flippable when their union is a convex quadrilateral. Replacing that edge by the quadrilateral's other diagonal preserves the vertex set and produces another triangulation. If the quadrilateral is not convex, the alternative diagonal does not give a valid local subdivision.
In 1936, You Watanabe established that the triangulations of a convex polygon form a connected exchange graph under diagonal flips. Her formulation represented each triangulation as a vertex of a finite graph and each permissible diagonal exchange as an edge, making connectivity a property of the entire family rather than of a particular decomposition. The result is equivalent to the existence of a finite flip sequence between any two triangulations of the same convex polygon.
For general planar point sets, the exchange structure depends on the geometry of the points. Klaus Wagner analyzed diagonal transformations of planar triangulations in the same period, relating local exchanges to the global connectivity of triangulation spaces. Charles Lawson later developed the flip process in a computational setting and connected it directly with the construction of Delaunay triangulations.
The number of flips required to pass between two triangulations defines their distance in the flip graph. For convex (n)-gons, the largest possible distance grows linearly with (n). Determining exact distances remains distinct from proving connectivity, because connectivity requires only the existence of a sequence, whereas distance concerns a shortest such sequence.
Delaunay triangulation
The Delaunay triangulation of a planar point set is characterized by an empty-circle condition. For every triangle in the triangulation, the open disk bounded by its circumcircle contains no point of the set. An equivalent local criterion states that an interior edge is Delaunay when the sum of the angles opposite that edge does not exceed (\pi).
When no four points are cocircular, the Delaunay triangulation is unique. Cocircular point sets can produce polygonal Delaunay faces with more than three vertices, and different triangulations of those faces satisfy the same empty-circle condition. The resulting nonuniqueness changes the chosen diagonals without changing the underlying Delaunay complex.
Boris Delaunay introduced the construction in 1934 through the geometry of empty spheres. In two dimensions, the triangulation is dual to the Voronoi diagram: a Delaunay edge joins two sites precisely when their Voronoi cells share an edge, while a Delaunay triangle corresponds to a Voronoi vertex at which three cells meet. Degenerate Voronoi vertices correspond to cocircular sets containing more than three sites.
Among all triangulations of a fixed planar point set, a Delaunay triangulation maximizes the smallest angle in lexicographic order. The statement does not imply that every triangle is close to equilateral, since the point distribution can force small angles. It instead means that no alternative triangulation has a larger minimum angle, and among triangulations tied at that angle, no alternative improves the next-smallest angle before worsening an earlier one.
The local edge criterion yields a relationship between Delaunay triangulations and flips. A non-Delaunay interior edge contained in a convex quadrilateral can be replaced by the opposite diagonal, after which the angle sequence improves. Repeated improvement terminates because a finite point set has only finitely many triangulations. This establishes both the geometric optimality of the Delaunay condition and the connection between local exchanges and global triangulation structure.
Topological formulation
A triangulation of a topological space (X) consists of a simplicial complex (K) together with a homeomorphism
[ |K|\longrightarrow X, ]
where (|K|) is the geometric realization of (K). In this setting, the triangles need not be planar Euclidean triangles inside a common plane. Their role is to provide combinatorial coordinate pieces whose gluings encode the topology of the space.
For a compact triangulated surface without boundary, each edge belongs to exactly two triangular faces. If (V), (E), and (F) denote the numbers of vertices, edges, and faces, then
[ 3F=2E. ]
Together with
[ V-E+F=\chi, ]
this relates the size of the triangulation to the Euler characteristic (\chi) of the surface. For the sphere, (\chi=2); for an orientable surface of genus (g), (\chi=2-2g).
Different triangulations can represent the same topological space. Pachner moves provide local transformations relating triangulations of the same piecewise-linear manifold. In dimension two, these transformations include diagonal flips and the insertion or deletion of a vertex inside a triangular face. Their higher-dimensional analogues replace one cluster of simplices by another cluster occupying the same polyhedral region.
Triangulability is automatic for many spaces encountered in elementary geometry, but it is not a universal property of arbitrary topological manifolds. Every two-dimensional manifold is triangulable, and three-dimensional manifolds possess compatible piecewise-linear structures. In higher dimensions, topological manifolds can fail to admit any simplicial triangulation, so the topological and piecewise-linear categories no longer coincide.
Computational structure
The computational treatment of triangulation distinguishes between constructing an arbitrary subdivision and constructing one that satisfies an additional geometric criterion. A simple polygon admits linear-time triangulation in the theoretical RAM model, although conceptually simpler ear-based methods have quadratic worst-case complexity. Delaunay triangulations of (n) planar points can be constructed in (O(n\log n)) time through divide-and-conquer methods, incremental methods, or algorithms based on the corresponding Voronoi diagram.
Triangulations provide finite representations of continuous domains. In the finite element method, a field over a region is approximated by functions defined separately on each triangle and matched across shared edges. In computer graphics, a surface mesh represents geometry through vertex coordinates and triangular face incidences. In both settings, the triangulation determines adjacency and local parameterization, while numerical accuracy also depends on geometric shape and on the approximation functions associated with the mesh.
Allowing additional vertices changes the admissible triangulations. Such vertices are called Steiner points, and they can refine a region where the original vertex set does not support the required element sizes or angle bounds. A triangulation with Steiner points is therefore not merely a different diagonalization of the original data; it is a subdivision with an enlarged vertex set and a correspondingly different combinatorial complex.