Show simple item record

dc.contributor.authorWessels, Mariette Christineen_US
dc.date.accessioned2017-06-07T08:01:44Z
dc.date.available2017-06-07T08:01:44Z
dc.date.issued2017-06-06en_US
dc.identifier.othervt_gsexam:11585en_US
dc.identifier.urihttp://hdl.handle.net/10919/77933
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_US
dc.format.mediumETDen_US
dc.publisherVirginia Techen_US
dc.rightsThis item is protected by copyright and/or related rights. Some uses of this item may be deemed fair and permitted by law even without permission from the rights holder(s), or the rights holder(s) may have licensed the work for use under certain conditions. For other uses you need to obtain permission from the rights holder(s).en_US
dc.subjectMinimum Weight Triangulationen_US
dc.subjectApproximation Algorithmen_US
dc.subjectGeometric Optimizationen_US
dc.titleA Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problemen_US
dc.typeThesisen_US
dc.contributor.departmentMathematicsen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelmastersen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineMathematicsen_US
dc.contributor.committeechairBrown, Ezra A.en_US
dc.contributor.committeememberFloyd, William J.en_US
dc.contributor.committeememberRaghvendra, Sharathen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record