On approximation behavior and implementation of the greedy triangulation for convex planar point sets

ABSTRACT

Manacher and Zorbrist conjectured that the greedy triangulation heuristic for minimum weight triangulation of n-point planar point sets yields solutions within an &Ogr;(n&egr;), &egr; < 1, factor of the optimum. We prove the conjecture in the case when the point set is convex by finding basic, geometric and combinatoric properties of greedy triangulations in the convex case. Our result contrasts with Kirkpatrick's &OHgr;(n) bound on the approximation factor of the Delauney triangulation heuristic which holds for convex, planar n-point sets. To support the conjecture of Manacher and Zorbrist, we also show that the greedy triangulation heuristic for minimum weight triangulation of a (non-necessarily convex) polygon yields solutions at most h times longer than the optimum where h is the diameter of the tree dual to the produced greedy triangulation of the polygon. On the other hand, we present an implementation of the greedy triangulation heuristic for an n-vertex convex point set or a convex polygon taking &Ogr;(n2) time and &Ogr;(n) space which improves Gilbert's &Ogr;(n2logn)-time and &Ogr;(n2)-space bound in this case. 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.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory, Verification