History of Triangulation Algorithms

Running Time	Designers	Year	Technique
O(n²)	*Lennes*	1911	Recursive diagonal insertion
O(n³)	*Meisters*	1975	Ear cutting
O(n log n)	*Garey, Johnson, Preparata & Tarjan*	1978	Decomposition into monotone pieces
O(n log n)	*Chazelle*	1982	Divide & Conquer
O( n + r log r) where r is the # of reflex vertices of the Polygon	*Hertel & Mehlhorn*	1983	-
O(n log s) where s is the sinuosity of P	*Chazelle*	1983	-
O(n log log n)	*Tarjan & Van Wyk*	1987	Using involved data structures
O(n (1 + to)) where to is the # of free triangles in the output triangulation.	Toussaint	1988	Sleeve-searching (Output sensitive)
O(n²)	ElGindy, Everett & Toussaint	1990	Finding an ear in linear time via prune & search
O(n)	*Chazelle*	1990	-
O(kn)	Kong, Everett & Toussaint	1990	Graham Scan