In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together. In most instances, the triangles of a triangulation are required to meet edge-to-edge and vertex-to-vertex.
Types
Different types of triangulations may be defined, depending both on what geometric object is to be subdivided and on how the subdivision is determined.
A triangulation of is a subdivision of into -dimensional simplices such that any two simplices in intersect in a common face or not at all, and any bounded set in intersects only finitely many simplices in. That is, it is a locally finitesimplicial complex that covers the entire space.
In cartography, a triangulated irregular network is a point set triangulation of a set of two-dimensional points together with elevations for each point. Lifting each point from the plane to its elevated height lifts the triangles of the triangulation into three-dimensional surfaces, which form an approximation of a three-dimensional landform.
A polygon triangulation is a subdivision of a given polygon into triangles meeting edge-to-edge, again with the property that the set of triangle vertices coincides with the set of vertices of the polygon. Polygon triangulations may be found in linear time and form the basis of several important geometric algorithms, including a simple approximate solution to the art gallery problem. The constrained Delaunay triangulation is an adaptation of the Delaunay triangulation from point sets to polygons or, more generally, to planar straight-line graphs.
In the finite element method, triangulations are often used as the mesh underlying a computation. In this case, the triangles must form a subdivision of the domain to be simulated, but instead of restricting the vertices to input points, it is allowed to add additional Steiner points as vertices. In order to be suitable as finite element meshes, a triangulation must have well-shaped triangles, according to criteria that depend on the details of the finite element simulation; for instance, some methods require that all triangles be right or acute, forming nonobtuse meshes. Many meshing techniques are known, including Delaunay refinement algorithms such as Chew's second algorithm and Ruppert's algorithm.
The concept of a triangulation may also be generalized somewhat to subdivisions into shapes related to triangles. In particular, a pseudotriangulation of a point set is a partition of the convex hull of the points into pseudotriangles, polygons that like triangles have exactly three convex vertices. As in point set triangulations, pseudotriangulations are required to have their vertices at the given input points.
