A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem

Given a set of n points on a plane, in the Minimum Weight Triangulation problem, we wish to find a triangulation that minimizes the sum of Euclidean lengths of its edges. The problem has been studied for more than four decades and is known to be incredibly challenging. In fact, the complexity status of this problem remained open until recently when it was shown to be NP-Hard. We present a novel polynomial-time algorithm that computes a 16-approximation of the minimum weight triangulation---a constant that is significantly smaller than what has been previously known.

To construct our candidate solution, our algorithm uses grids to partition edges into levels by increasing weights, so that edges with similar weights appear in the same level. We incrementally triangulate the point set by constructing a growing partial triangulation for each level, introducing edges in increasing order of level. At each level, we use a variant of the ring heuristic followed by a greedy heuristic to add edges, finally resulting in a complete triangulation of the point set. In our analysis, we reduce the problem of comparing the weight of the candidate and the optimal solutions to a comparison between the cardinality of the two underlying graphs. We develop a new technique to compare the cardinality of planar straight-line graphs, and in combination with properties due to the imposed grid structure, we bound the approximation ratio.