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

Sharath Raghvendra, Mariëtte C. Wessels

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 inc…