Incomputational geometry,polygon triangulation is thepartition of apolygonal area (simple polygon)P into a set oftriangles,^[1] i.e., finding a set of triangles with pairwise non-intersecting interiors whoseunion isP.

Triangulations may be viewed as special cases ofplanar straight-line graphs. When there are no holes or added points, triangulations formmaximal outerplanar graphs.

Over time, a number of algorithms have been proposed to triangulate a polygon.

It is trivial to triangulate anyconvex polygon inlinear time into afan triangulation, by adding diagonals from one vertex to all other non-nearest neighbor vertices.

The total number of ways to triangulate a convexn-gon by non-intersecting diagonals is the (n−2)ndCatalan number, which equals

${\displaystyle \frac{n(n+1)...(2n-4)}{(n-2)!}}$,

a formula found byLeonhard Euler.^[2]

One way to triangulate asimple polygon is based on thetwo ears theorem, as the fact that any simple polygon with at least 4 vertices without holes has at least two "ears", which are triangles with two sides being the edges of the polygon and the third one completely inside it.^[3] The algorithm then consists of finding such an ear, removing it from the polygon (which results in a new polygon that still meets the conditions) and repeating until there is only one triangle left.

This algorithm is easy to implement, but slower than some other algorithms, and it only works on polygons without holes. An implementation that keeps separate lists of convex and concave vertices will run inO(n²) time. This method is known asear clipping and sometimesear trimming. An efficient algorithm for cutting off ears was discovered by Hossam ElGindy, Hazel Everett, andGodfried Toussaint.^[4]

A simple polygon is monotone with respect to a lineL, if any line orthogonal toL intersects the polygon at most twice. Amonotone polygon can be split into two monotonechains. A polygon that is monotone with respect to the y-axis is calledy-monotone. A monotone polygon withn vertices can be triangulated inO(n) time. Assuming a given polygon is y-monotone, thegreedy algorithm begins by walking on one chain of the polygon from top to bottom while adding diagonals whenever it is possible.^[1] It is easy to see that the algorithm can be applied to any monotone polygon.

A monotone polygon can be triangulated in linear time with either the algorithm ofA. Fournier and D.Y. Montuno,^[5] or the algorithm ofGodfried Toussaint.^[6]

If a polygon is not monotone, it can be partitioned into monotone subpolygons inO(n logn) time using asweep-line approach. The algorithm does not require the polygon to be simple, thus it can be applied topolygons with holes.Generally, this algorithm can triangulate a planar subdivision withn vertices inO(n logn) time usingO(n) space.^[1]

A useful graph that is often associated with a triangulation of a polygonP is thedual graph. Given a triangulationT_P ofP, one defines the graphG(T_P) as the graph whose vertex set are the triangles ofT_P, two vertices (triangles) being adjacent if and only if they share a diagonal. It is easy to observe thatG(T_P) is atree with maximum degree 3.

Until 1988, whether asimple polygon can be triangulated faster thanO(n logn) time was an open problem in computational geometry.^[1] Then,Tarjan & Van Wyk (1988) discovered anO(n log logn)-time algorithm for triangulation,^[7] later simplified byKirkpatrick, Klawe & Tarjan (1992).^[8] Several improved methods with complexityO(n log^*n) (in practice, indistinguishable fromlinear time) followed.^[9][10][11]

Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.^[12] A simpler randomized algorithm with linear expected time is also known.^[13]

Seidel's decomposition algorithm^[10] and Chazelle's triangulation method are discussed in detail inLi & Klette (2011).^[14]

Thetime complexity of triangulation of ann-vertex polygonwith holes has anΩ(n logn)lower bound, in algebraiccomputation tree models of computation.^[1] It is possible to compute the number of distinct triangulations of a simple polygon in polynomial time usingdynamic programming, and (based on this counting algorithm) to generateuniformly random triangulations in polynomial time.^[15] However, counting the triangulations of a polygon with holes is#P-complete, making it unlikely that it can be done in polynomial time.^[16]

• Both triangulation problems are a special case oftriangulation (geometry) and a special case ofpolygon partition.
• Minimum-weight triangulation is a triangulation in which the goal is to minimize the total edge length.
• Apoint-set triangulation is a polygon triangulation of the convex hull of a set of points. ADelaunay triangulation is another way to create a triangulation based on a set of points.
• Theassociahedron is a polytope whose vertices correspond to the triangulations of a convex polygon.
• Polygon triangle covering, in which the triangles may overlap.
• Tiling by polygons, where the goal is to cover the entire plane with polygons of pre-specified shapes.

• Nonzero-rule
• Catalan number
• Planar graph
• Flip graph

• Demo as Flash swf, A Sweep Line algorithm.
• Song Ho's explanation of the OpenGL GLU tesselator

• Triangulation (geometry)

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata