Editing Polygon triangulation (section)

== Polygon triangulation without extra vertices ==
Over time, a number of algorithms have been proposed to triangulate a polygon.

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

=== Ear clipping method ===
[[Image:Polygon-ear.png|thumb|A polygon ear]]
One way to triangulate a simple polygon is based on the [[two ears theorem]], as the fact that any simple polygon with at least 4 vertices without holes has at least two "[[Ear (mathematics)|ear]]s", which are triangles with two sides being the edges of the polygon and the third one completely inside it.<ref>{{citation
| first1=Gary Hosler | last1=Meisters
| title=Polygons have ears
| journal=[[American Mathematical Monthly]]
| volume=82
| year=1975
| issue=6
| pages=648–651
| url=https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1053&context=mathfacpub
| doi=10.2307/2319703| jstor=2319703
}}</ref> 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 in {{math|O(<var>n</var><sup>2</sup>)}} time. This method is known as ''ear clipping'' and sometimes ''ear trimming''. An efficient algorithm for cutting off ears was discovered by Hossam ElGindy, Hazel Everett, and [[Godfried Toussaint]].<ref>{{citation
| last1 = ElGindy | first1 = Hossam
| last2 = Everett | first2 = Hazel
| last3 = Toussaint | first3 = Godfried T.
| year = 1993
| title = Slicing an ear using prune-and-search
| journal = Pattern Recognition Letters
| volume = 14
| issue = 9
| pages = 719–722
| doi=10.1016/0167-8655(93)90141-y| bibcode = 1993PaReL..14..719E
}}</ref>

=== Monotone polygon triangulation ===
[[Image:Polygon-to-monotone.png|thumb|Breaking a polygon into monotone polygons]]

A simple polygon is monotone with respect to a line {{math|L}}, if any line orthogonal to {{math|L}} intersects the polygon at most twice. A monotone polygon can be split into two monotone ''chains''. A polygon that is monotone with respect to the y-axis is called ''y-monotone''. A monotone polygon with {{math|n}} vertices can be triangulated in {{math|O(<var>n</var>)}} time. Assuming a given polygon is y-monotone, the [[greedy algorithm]] begins by walking on one chain of the polygon from top to bottom while adding diagonals whenever it is possible.<ref name= bkos/> It is easy to see that the algorithm can be applied to any monotone polygon.

=== Triangulating a non-monotone polygon ===
If a polygon is not monotone, it can be partitioned into monotone subpolygons in {{math|O(<var>n</var> log <var>n</var>)}} time using a [[Sweep line algorithm|sweep-line approach]]. The algorithm does not require the polygon to be simple, thus it can be applied to [[Polygon with holes|polygons with holes]].
Generally, this algorithm can triangulate a planar subdivision with {{math|<var>n</var>}} vertices in {{math|O(<var>n</var> log <var>n</var>)}} time using {{math|O(<var>n</var>)}} space.<ref name= bkos/>

=== Dual graph of a triangulation ===
A useful graph that is often associated with a triangulation of a polygon {{math|<var>P</var>}} is the [[dual graph]]. Given a triangulation {{math|<var>T<sub>P</sub></var>}} of {{math|<var>P</var>}}, one defines the graph {{math|<var>G</var>(<var>T<sub>P</sub></var>)}} as the graph whose vertex set are the triangles of {{math|<var>T<sub>P</sub></var>}}, two vertices (triangles) being adjacent if and only if they share a diagonal. It is easy to observe that {{math|<var>G</var>(<var>T<sub>P</sub></var>)}} is a [[Tree (graph theory)|tree]] with maximum degree 3.

=== Computational complexity ===
Until 1988, whether a [[simple polygon]] can be triangulated faster than {{math|O(<var>n</var> log <var>n</var>)}} time was an open problem in computational geometry.<ref name= bkos/> Then, {{harvtxt|Tarjan|Van Wyk|1988}} discovered an {{math|O(<var>n</var> log log <var>n</var>)}}-time algorithm for triangulation,<ref>{{citation
 | last1 = Tarjan | first1 = Robert E. | author1-link = Robert Tarjan
 | last2 = Van Wyk | first2 = Christopher J.
 | doi = 10.1137/0217010
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 925194
 | pages = 143–178
 | title = An O(''n'' log log ''n'')-time algorithm for triangulating a simple polygon
 | volume = 17
 | year = 1988| citeseerx = 10.1.1.186.5949}}</ref> later simplified by {{harvtxt|Kirkpatrick|Klawe|Tarjan|1992}}.<ref>{{citation
 | last1 = Kirkpatrick | first1 = David G. | author1-link = David G. Kirkpatrick
 | last2 = Klawe | first2 = Maria M. | author2-link = Maria Klawe
 | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan
 | doi = 10.1007/BF02187846
 | issue = 4
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1148949
 | pages = 329–346
 | title = Polygon triangulation in O(''n'' log log ''n'') time with simple data structures
 | volume = 7
 | year = 1992| doi-access = free
 }}</ref> Several improved methods with complexity {{math|[[Big O notation#Orders of common functions|O(<var>n</var> log<sup>*</sup> <var>n</var>)]]}} (in practice, indistinguishable from [[linear time]]) followed.<ref>{{citation
 | last1 = Clarkson | first1 = Kenneth L. | author1-link = Kenneth L. Clarkson
 | last2 = Tarjan | first2 = Robert | author2-link = Robert Tarjan
 | last3 = van Wyk | first3 = Christopher J.
 | doi = 10.1007/BF02187741
 | journal = [[Discrete & Computational Geometry]]
 | pages = 423–432
 | title = A fast Las Vegas algorithm for triangulating a simple polygon
 | volume = 4
 | issue = 5 | year = 1989| doi-access = free
 }}</ref><ref name="Seidel">{{citation
| last=Seidel | first=Raimund | author-link= Raimund Seidel
| title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons
| journal=[[Computational Geometry (journal)|Computational Geometry]]
| volume=1
| year=1991
| pages=51–64
| doi=10.1016/0925-7721(91)90012-4 | doi-access = free| citeseerx=10.1.1.55.5877
}}</ref><ref>{{citation
 | last1 = Clarkson | first1 = Kenneth L. | author1-link = Kenneth L. Clarkson
 | last2 = Cole | first2 = Richard
 | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan
 | doi = 10.1142/S0218195992000081
 | issue = 2
 | journal = International Journal of Computational Geometry & Applications
 | mr = 1168952
 | pages = 117–133
 | title = Randomized parallel algorithms for trapezoidal diagrams
 | volume = 2
 | year = 1992}}</ref>

[[Bernard Chazelle]] showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.<ref>{{citation
| last=Chazelle | first=Bernard | author-link=Bernard Chazelle
| title=Triangulating a Simple Polygon in Linear Time
| journal=[[Discrete & Computational Geometry]]
| volume=6
| issue=3
| year=1991
| pages=485–524
| issn=0179-5376
| doi=10.1007/BF02574703 | doi-access=free}}</ref> A simpler randomized algorithm with linear expected time is also known.<ref>{{citation
 |last1        = Amato
 |first1       = Nancy M.
 |author1-link = Nancy M. Amato
 |last2        = Goodrich
 |first2       = Michael T.
 |author2-link = Michael T. Goodrich
 |last3        = Ramos
 |first3       = Edgar A.
 |title        = A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time
 |journal      = [[Discrete & Computational Geometry]]
 |volume       = 26
 |year         = 2001
 |pages        = 245–265
 |issn         = 0179-5376
 |doi          = 10.1007/s00454-001-0027-x
 |doi-access   = free
 |issue        = 2
 }}</ref>

Seidel's decomposition algorithm<ref name="Seidel" /> and Chazelle's triangulation method are discussed in detail in {{harvtxt|Li|Klette|2011}}.<ref>{{citation
| last1 = Li | first1 = Fajie
| last2 = Klette | first2 = Reinhard
| title = Euclidean Shortest Paths
| publisher = [[Springer (publisher)|Springer]]
| doi = 10.1007/978-1-4471-2256-2
| isbn = 978-1-4471-2255-5
| year = 2011}}</ref>

The [[time complexity]] of triangulation of an {{math|<var>n</var>}}-vertex polygon ''with'' holes has an {{math|Ω(<var>n</var> log <var>n</var>)}} [[lower bound]], in algebraic [[computation tree]] models of computation.<ref name= bkos/> It is possible to compute the number of distinct triangulations of a simple polygon in polynomial time using [[dynamic programming]], and (based on this counting algorithm) to generate [[discrete uniform distribution|uniformly random]] triangulations in polynomial time.<ref>{{citation
| last1 = Epstein | first1 = Peter
| last2 = Sack | first2 = Jörg-Rüdiger | author2-link = Jörg-Rüdiger Sack
| doi = 10.1145/189443.189446
| issue = 3
| journal = ACM Transactions on Modeling and Computer Simulation
| pages = 267–278
| title = Generating triangulations at random
| volume = 4
| year = 1994| s2cid = 14039662}}</ref> However, counting the triangulations of a polygon with holes is [[♯P-complete|#P-complete]], making it unlikely that it can be done in polynomial time.<ref>{{citation
| last = Eppstein | first = David | author-link = David Eppstein
| arxiv = 1903.04737
| contribution = Counting polygon triangulations is hard
| doi = 10.4230/LIPIcs.SoCG.2019.33
| pages = 33:1–33:17
| publisher = Schloss Dagstuhl
| series = Leibniz International Proceedings in Informatics (LIPIcs)
| title = Proc. 35nd Int. Symp. Computational Geometry
| year = 2019
| volume = 129 | doi-access = free | isbn = 9783959771047 | s2cid = 75136891}}</ref>