• home
• current students
• graduate
• events

Presenter: Yue Fang
Supervisor:

Date: Tue, March 27, 2018
Time: 13:00:00 - 14:30:00
Place: Engineering Office Wing Room 430

ABSTRACT

ABSTRACT: 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. In our work, 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. We have proven our proposed methods can satisfy a stronger optimality condition than 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.