Greedy is as Good as Delaunay (Almost)

Wolfgang Mulzer, Paul Seiferth

Let S be a planar point set. Krznaric and Levcopoulos proved that given the Delaunay triangulation DT(S) for S, one can find the greedy triangulation GT(S) in linear time. We provi…