A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem
Sharath Raghvendra, Mariëtte C. Wessels · Society for Industrial and Applied Mathematics eBooks · 2018
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 length of its edges. This incredibly challenging problem has been studied for more than four decades and has been only recently shown to be NP-Hard. In this paper we present a novel polynomial-time algorithm that computes an expected 14-approximation of the minimum weight triangulation—a constant that is significantly smaller than what has been previously known. For every integer q ≥ 1, we also show that our triangulation is simultaneously a 14-approximation of a triangulation that minimizes the q-norm of its edge costs, i.e., the sum of qth powers of all its edges. In our algorithm, we use grids to partition the edges into levels where shorter edges appear at smaller levels and edges with similar lengths appear at the same level. We then triangulate the point set incrementally by introducing edges in increasing order of their levels. We introduce the edges of any level i + 1 in two steps. In the first step, we partition the boundary of any non-triangulated face into reflex chains and add edges between successive chains using a variant of the well-known ring heuristic to generate a partial triangulation Âi. In the second step, we greedily add non-intersecting level i + 1 edges to Âi in increasing order of their length and obtain a partial triangulation Âi+1. The ring heuristic is known to yield only an