History of Triangulation Algorithms

 

Running Time

Designers

Year

Technique

O(n2)

Lennes

1911

Recursive diagonal insertion

O(n3)

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(n2)

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.

Back to Art Gallery Home Page | Demo Applet