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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Mathematics

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2017

Author dc:creator

• Wessels, Mariette Christine

Chair dc:contributor.committeechair

• Brown, Ezra A.

Committee members dc:contributor.committeemember

• Floyd, William J.
• Raghvendra, Sharath

• Minimum Weight Triangulation
• Approximation Algorithm
• Geometric Optimization

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

vt_gsexam:11585

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/77933