Polygon triangulation

When there are no holes or added points, triangulations form maximal outerplanar graphs.

An efficient algorithm for cutting off ears was discovered by Hossam ElGindy, Hazel Everett, and Godfried Toussaint.

Generally, this algorithm can triangulate a planar subdivision with n vertices in O(n log n) time using O(n) space.

Until 1988, whether a simple polygon can be triangulated faster than O(n log n) time was an open problem in computational geometry.

[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.

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

[1] 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 uniformly random triangulations in polynomial time.