Author(s):
Montagner, Arnaldo Jovanini
Date: 2007
Persistent ID: https://hdl.handle.net/20.500.12733/1606196
Origin: Oasisbr
Subject(s): Estruturas de dados (Computação); Geometria computacional; Teoria dos grafos; Topologia; Data structures (Computer science); Computational geometry; Graph theory; Topology; Estruturas de dados (Computação); Estruturas de dados (Computação); Geometria computacional; Geometria computacional; Teoria dos grafos; Teoria dos grafos; Topologia; Topologia; Data structures (Computer science); Data structures (Computer science); Computational geometry; Computational geometry; Graph theory; Graph theory; Topology; Topology
Description
Orientador: Jorge Stolfi [Orientador]
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação.
Resumo: Mapas são subdivisões de espaços topológicos em regiões simples, e triangulações são um tipo específico de mapa em que cada elemento é um simplexo (aresta, triângulo, tetraedro, etc). Neste trabalho, tratamos o problema de representação da topologia de triangulações e mapas de dimensão arbitrária. Estudamos a utilização de uma representação baseada em grafos de arestas coloridas, já utilizada como ferramenta teórica, mas nunca empregada em aplicações práticas. A principal limitação desta representação é a relativa inflexibilidade imposta sobre a manipulação da topologia. Há porém grandes vantagens em sua utilização, como a simplicidade de representação e a generalidade. Este trabalho consiste na especificação teórica de uma estrutura de dados baseada nestes grafos coloridos e de operações topológicas para construção e manipulação da estrutura. A utilização desta estrutura é ilustrada através de algoritmos para resolução de problemas em geometria computacional
Abstract: Maps are subdivisions of topological spaces into simple regions, and triangulations are a specific kind of map wherein each element is a simplex (edge, triangle, tetrahedron, etc). In this work, we analyze the problem of representing the topology of triangulations and maps with arbitrary dimension. We study a representation based on edge-colored graphs, already used as theoretical tool, but never employed in practical applications. The main limitation of this representation is the relative inexibility imposed on the manipulation of topology. There are, though, great advantages in its use, as its simplicity and generality. This work consists in the theoretic specification of a data structure based on these colored graphs and of topological operators to build and manipulate the structure.The use of this structure is illustrated by algorithms for computational geometry problems
Doutorado
Computação Gráfica
Mestre em Ciência da Computação
