Triangulation (geometry)

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. 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 (a simplex of any lower dimension) or not at all, and any bounded set in intersects only finitely many simplices in . That is, it is a locally finite simplicial complex that covers the entire space. A point-set triangulation, i.e., a triangulation of a discrete set of points , is a subdivision of the convex hull of the points into simplices such that any two simplices intersect in a common face of any dimension or not at all and such that the set of vertices of the simplices are contained in . Frequently used and studied point set triangulations include the Delaunay triangulation (for points in general position, the set of simplices that are circumscribed by an open ball that contains no input points) and the minimum-weight triangulation (the point set triangulation minimizing the sum of the edge lengths). 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.