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 Ω(n~(1/2)) 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.
展开▼
