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 triangul ation and the minimum weight triangulation? 2. Is there a polynomial t ime algorithm that always produces a triangulation whose length is wit hin a constant factor from the minimum? The answer to the first questi on is that the known Omega(root n) lower bound is tight. The second qu estion is answered in the affirmative by using a slight modification o f 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 obt ained within the same time bounds. (C) 1998 Academic Press.