A Constant-Factor Approximation for Maximum Weight Triangulation
Shiyan Hu · 2003
The paper is the first report on approximation algorithms for computing the maximum weight triangulation of a set of n points in the plane. We prove an Ω( √ n) lower bound on the approximation factor for several heuristics: maximum greedy triangulation, maximum greedy spanning tree triangulation and maximum spanning tree triangulation. We then propose the Spoke Triangulation algorithm, which always approximates the maximum weight triangulation for points in general position within a factor of six and can be computed in O(n log n) time. We also prove that Spoke Triangulation approximates the maximum weight triangulation of a convex polygon within a factor of two.