Running Time 
Designers 
Year 
Technique 
O(n^{2}) 
Lennes 
1911 
Recursive diagonal insertion 
O(n^{3}) 
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) 
Hertel & Mehlhorn 
1983 
 
O(n log s) 
Chazelle 
1983 
 
O(n log log n) 
Tarjan & Van Wyk 
1987 
Using involved data structures 
O(n (1 + to)) 

1988 
Sleevesearching 
O(n^{2}) 
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 
The data in this table was taken from a Computational
Geometry (cs507)
lecture given by G.Toussaintat
McGill's School of Computer Science.