An ω(√n) lower bound for the nonoptimality of the greedy triangulation

Gilbert, 1979, New results in planar triangulations Kirkpatrick, 1980, A note on Delaunay and optimal triangulations, Inform. Process. Lett., 10, 127, 10.1016/0020-0190(80)90062-9 Klincsek, 1980, Minimal triangulations of polygonal domains, Ann. Discrete Math., 9, 121, 10.1016/S0167-5060(08)70044-X C. Levcopoulos and A. Lingas, On approximation behavior of the greedy triangulation for convex polygons, Algorithmica, to appear. Lingas, 1985, A linear-time heuristic for minimum weight triangulation of convex polygons Lingas, 1986, The greedy and Delaunay triangulations are not bad in the average case, Inform. Process. Lett., 22, 25, 10.1016/0020-0190(86)90038-4 Lingas, 1986, On approximation behavior and implementation of the greedy triangulation for convex planar point sets Lloyd, 1977, On triangulations of a set of points in the plane Manacher, 1979, Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation, Inform. Process. Lett., 9, 31, 10.1016/0020-0190(79)90104-2 Manacher, 1982 Preparata, 1985, Computational Geometry, An Introduction