On approximation behavior of the greedy triangulation for convex polygons (Q1098295)

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor of the optimum. - The authors have proved this result independently at the same time. Recently, the result has been generalized by showing that for any polygon P with r reflex angles, the greedy triangulation heuristic yields solutions within an O(r) factor of the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's \(\Omega\) (n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convex, n-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for an n-vertex convex point set or a convex polygon taking \(O(n^ 2)\) time and O(n) space. To derive the latter result, we show that given a convex polygon P, one can find for all vertices v of P a shortest diagonal of P incident to v in linear time. Finally, we observe that the greedy triangulation for convex polygons having so called semi-circular property can be constructed in time O(n log n).