Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:SSU.etd-08232005-111957 |
| Date | 23 August 2005 |
| Creators | Vassilev, Tzvetalin Simeonov |
| Contributors | Vassileva, Julita, Urrutia, Jorge, Marshall, Murray, Keil, J. Mark, Eramian, Mark G., Cheston, Grant A. |
| Publisher | University of Saskatchewan |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://library.usask.ca/theses/available/etd-08232005-111957/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to University of Saskatchewan or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0022 seconds