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

dc.contributor.authorWessels, Mariette Christineen
dc.contributor.committeechairBrown, Ezra A.en
dc.contributor.committeememberFloyd, William J.en
dc.contributor.committeememberRaghvendra, Sharathen
dc.contributor.departmentMathematicsen
dc.date.accessioned2017-06-07T08:01:44Zen
dc.date.available2017-06-07T08:01:44Zen
dc.date.issued2017-06-06en
dc.description.abstractGiven 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.en
dc.description.degreeMaster of Scienceen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:11585en
dc.identifier.urihttp://hdl.handle.net/10919/77933en
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectMinimum Weight Triangulationen
dc.subjectApproximation Algorithmen
dc.subjectGeometric Optimizationen
dc.titleA Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problemen
dc.typeThesisen
thesis.degree.disciplineMathematicsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Wessels_MC_T_2017.pdf
Size:
1020.69 KB
Format:
Adobe Portable Document Format
Collections