Regular triangulations and applications

Author(s)

Fernando Bissi Pires

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2008-06-27

Examining board members

Luis Gustavo Nonato; Rosane Minghim; Helio Pedrini

• Advisor: Luis Gustavo Nonato

Abstract

Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work (AU)