Anais do X SIBGRAPI (1997) #ART58


Novos Resultados em Triangulações (Triangulação Gulosa)

Luiz M. G. Gonçalves
Laboratório de Computação Gráfica - COPPE-UFRJ

Abstract. This paper describes a data structure with a restricted set of topological operations (creation, subdivision, and flip) used to construct planar triangulations. We discuss the implementation of algorithms to build some common triangulations (greedy, Delaunay, and rectangular adaptive) based on that structure. In order to allow the use of such a structure in the implementation of the Greedy Triangulation (GT), we define a new concept of GT and present an algorithm to build it. This GT algorithm has the same complexity as the best known algorithm for the traditional GT.

[ full version | contact authors ]