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. / Master of Science / Given a set of n points on a plane P, a triangulation of P is a set of edges such that no two edges intersect at a point not in P, and the edges subdivide the convex hull of P into triangles. Triangulations have a variety of applications, including computer graphics, finite element analysis, and interpolation, which motivates the need for efficient algorithms to compute triangulations with desirable qualities. The Minimum Weight Triangulation problem is the problem of computing the triangulation T that minimizes the sum of Euclidean lengths of its edges and performs well in many of the above-mentioned applications. 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. The algorithm makes use of grids together with a variant of the ring and greedy heuristic adapted to apply in a new setting, resulting in an elegant, efficient algorithm.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/77933 |
| Date | 06 June 2017 |
| Creators | Wessels, Mariette Christine |
| Contributors | Mathematics, Brown, Ezra A., Floyd, William J., Raghvendra, Sharath |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0021 seconds