Editing Polygon triangulation (section)

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