Quasi-greedy triangulations approximating the minimum weight triangulation

This article settles the following two longstanding open problems: 1. What is the worst case approximation ratio between the greedy triangulation and the minimum weight triangulation? 2. Is there a polynomial time algorithm that always produces a triangulation whose length is within a constant factor from the minimum? The answer to the first question is that the known Omega(root n) lower bound is tight. The second question is answered in the affirmative by using a slight modification of an O(n log n) algorithm for the greedy triangulation. We also derive some other interesting results. For example, we show that a constant-factor approximation of the minimum weight convex partition can be obtained within the same time bounds. (C) 1998 Academic Press.