triangulations

Triangulation is a way of breaking down a geometric object into simplices, typically triangles in two dimensions. In topology, a triangulation of a space is a simplicial complex together with a homeomorphism from its underlying polyhedron to the space. In computational geometry and mesh generation, a triangulation of a finite set of points in the plane is a maximal planar straight-line graph whose vertices are the given points and whose faces are triangles; its union covers the convex hull of the points.

In a polygon triangulation, a simple polygon is divided into non-overlapping triangles whose vertices lie on the polygon’s vertices. Every n-vertex simple polygon has a triangulation with n-2 triangles, and ear clipping is a classic algorithm for this task. For monotone polygons, linear-time algorithms exist.

For a finite set of points in the plane in general position, a triangulation is a partition of the convex hull into triangles with vertices from the set; the number of triangles is 2n - 2 - h, where n is the number of points and h is the number of hull vertices. Such triangulations form planar straight-line graphs that extend to cover the hull and, in combination with boundary edges, describe a mesh.

Delaunay triangulation is a prominent, widely used triangulation that maximizes the minimum angle and satisfies the empty circumcircle property. It is closely related to Voronoi diagrams and is a standard choice for mesh generation. Constrained triangulations incorporate prescribed edges, preserving boundaries or interior constraints in the mesh.

Construction methods include Bowyer–Watson incremental insertion, divide-and-conquer, and edge-flipping approaches for Delaunay triangulations; polygon triangulation uses ear clipping or monotone subdivisions. Complexity ranges from near-linear to quadratic, depending on data and constraints.

Triangulations underpin finite element analysis, computer graphics, terrain modeling, and geographic information systems. They also generalize to higher dimensions as simplicial decompositions of manifolds and polyhedral spaces.