The problem of selecting the connectivity of a triangulation in order to minimize a given cost function is studied. This problem is of great importance for applications, such as generating triangle mesh models of images and other bivariate functions. In early work, a well-known method named the local optimization procedure (LOP) was proposed by Lawson for solving the triangulation optimization problem. More recently, Yu et al. proposed a variant of the LOP called the LOP with lookahead (LLOP), which has proven to be more effective than the LOP. Unfortunately, each of the LOP and LLOP can only guarantee to yield triangulations that satisfy a weak optimality condition for most cost functions. That is, the triangulation optimized by the LOP or LLOP is only guaranteed to be such that no single edge flip can reduce the triangulation cost. In this thesis, a new optimality criterion named n-flip optimality is proposed, which has proven to be a useful tool for analyzing the optimality property. We propose a more general framework called the modified LOP (MLOP), with several free parameters, that can be used to solve the triangulation-cost optimization problem. By carefully selecting the free parameters, two MLOP-based methods called the MLOPB(L,M) and MLOPC(L) are derived from this framework. According to the optimality property introduced in the thesis, we have proven our proposed methods can satisfy a stronger optimality condition than the LOP and LLOP. That is, the triangulation produced by our MLOP-based methods cannot have their cost reduced by any single edge flip or any two edge flips. Due to satisfying this stronger optimality condition, our proposed methods tend to yield triangulations of significantly lower cost than the LOP and LLOP methods.
In order to evaluate the performance of our MLOP-based methods, they are compared with two other competing approaches, namely the LOP and LLOP. Experimental results show that the MLOPB and MLOPC methods consistently yield triangulations of much lower cost than the LOP and LLOP. More specifically, our MLOPB and MLOPC methods yield triangulations with an overall median cost reduction of 16.36% and 16.62%, respectively, relative to the LOP, while the LLOP can only yield triangulations with an overall median cost reduction of 11.49% relative to the LOP. Moreover, our proposed methods MLOPB(2,i) and MLOPA(i) are shown to produce even better results if the parameter i is increased at the expense of increased computation time. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/9277 |
| Date | 30 April 2018 |
| Creators | Fang, Yue |
| Contributors | Adams, Michael D. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0025 seconds