Editing Polygon triangulation (section)

=== Special cases ===
[[File:Polygon Triangulations (heptagon).svg|thumb|The 42 possible triangulations for a [[convex region|convex]] [[heptagon]] (7-sided convex polygon). This number is given by the 5th [[Catalan number]].]]
It is trivial to triangulate any [[convex polygon]] in [[linear time]] into a [[fan triangulation]], by adding diagonals from one vertex to all other non-nearest neighbor vertices.

The total number of ways to triangulate a convex [[Polygon|''n''-gon]] by non-intersecting diagonals is the (''n''−2)nd [[Catalan number]], which equals
:<math>\frac{n(n+1)...(2n-4)}{(n-2)!}</math>,
a formula found by [[Leonhard Euler]].<ref>{{citation|author-link=Clifford Pickover|last=Pickover|first= Clifford A.|title=The Math Book|publisher= Sterling|year= 2009|page= 184}}</ref>

A [[monotone polygon]] can be triangulated in linear time with either the algorithm of  [[Alain Fournier (academic)|A. Fournier]] and D.Y. Montuno,<ref>{{citation
| last1=Fournier | first1=Alain | author1-link=Alain Fournier (academic)
| last2=Montuno |first2= Delfin Y.
| title=Triangulating simple polygons and equivalent problems
| journal=[[ACM Transactions on Graphics]]
| volume=3
| issue=2
| year=1984
| pages=153–174
| issn=0730-0301
| doi=10.1145/357337.357341|s2cid=33344266 | doi-access=free
}}</ref> or the algorithm of [[Godfried Toussaint]].<ref>{{citation
| first1=Godfried T. | last1=Toussaint
| year=1984
| title=A new linear algorithm for triangulating monotone polygons
| journal=Pattern Recognition Letters
| volume=2
| issue=3
| pages=155–158
| doi=10.1016/0167-8655(84)90039-4| bibcode=1984PaReL...2..155T
}}</ref>