Editing Triangulation (geometry)

{{Short description|Subdivision of a planar object into triangles}}
{{refimprove|date=May 2024}}

In [[geometry]], a '''triangulation''' is a subdivision of a [[plane (geometry)|planar object]] into triangles, and by extension the subdivision of a higher-dimension geometric object into [[simplex|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 <math>T</math> of <math>\mathbb{R}^d</math> is a subdivision of <math>\mathbb{R}^d</math> into <math>d</math>-dimensional simplices such that any two simplices in <math>T</math> intersect in a common face (a simplex of any lower dimension) or not at all, and any [[bounded set]] in <math>\mathbb{R}^d</math> intersects only [[finite set|finite]]ly many simplices in <math>T</math>. 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 space|discrete]] set of points <math>\mathcal{P}\subset\mathbb{R}^d</math>, is a subdivision of the [[convex hull]] of the points into simplices such that any two simplices intersect in a common [[Face (geometry)|face]] of any dimension or not at all and such that the set of vertices of the simplices are contained in <math>\mathcal{P}</math>.<ref>{{Cite book |last=De Loera |first=Jesús A. |author-link=Jesús A. De Loera |title=Triangulations, Structures for Algorithms and Applications |last2=Rambau |first2=Jörg |last3=Santos |first3=Francisco |author-link3=Francisco Santos Leal |publisher=Springer |year=2010 |isbn=9783642129711 |volume=25}}</ref> 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.<ref>{{Cite book |last=Berg |first=Mark Theodoor de |title=Computational geometry: algorithms and applications |last2=Kreveld |first2=Marc van |last3=Overmars |first3=Mark H. |last4=Schwarzkopf |first4=Otfried |date=2000 |publisher=Springer |isbn=978-3-540-65620-3 |edition=2 |location=Berlin Heidelberg |pages=45-61}}</ref> 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 graph]]s.
* A Euclidean [[Surface triangulation|triangulation of a surface]] <math>\Sigma</math> is a set of subset of compact spaces <math>T_\alpha</math> of <math>\Sigma</math> homeomorphic to a non degenerate triangle in <math>\R^2</math> via <math>f_\alpha</math> such that they cover the entire surface, the intersection on any pair of subsets is either empty, an edge or a vertex and if the intersection the intersection <math>T_\alpha \cap T_\beta</math>  is not empty then  <math>f_{\alpha}f_{\beta}^{-1} </math> is an isometry of the plane  on that intersection.<ref>{{Cite book |last=Papadopoulos |first=Athanase |title=Handbook of Teichmüller Theory |publisher=European Mathematical Society |isbn=9783037190296 |publication-date=2007 |page=510}}</ref> 
* In the [[finite element method]], triangulations are often used as the [[polygon mesh|mesh]] (in this case, a [[triangle 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 point (computational geometry)|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 (see [[Types of mesh#Mesh quality|mesh quality]]); for instance, some methods require that all triangles be right or acute, forming [[nonobtuse mesh]]es. Many meshing techniques are known, including [[Delaunay refinement]] algorithms such as [[Chew's second algorithm]] and [[Ruppert's algorithm]].
* In more general topological spaces, [[Triangulation (topology)|triangulations]] of a space generally refer to simplicial complexes that are [[homeomorphic]] to the space.<ref>{{Cite book |last=Basener |first=William F. |url=http://dx.doi.org/10.1002/9780470067949 |title=Topology and Its Applications |date=2006-10-20 |publisher=Wiley |isbn=978-0-471-68755-9 |pages=3-14}}</ref>

==Generalization==
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.

==References==
{{reflist}}

==External links==
* {{mathworld | urlname = Triangulation | title = Triangulation}}

[[Category:Triangulation (geometry)| ]]