Vicente Helano Feitosa Batista
Resumo
O objetivo principal desta tese é obter uma estrutura de dados capaz de representar triangulações bidimensionais, diminuindo a redundância no armazenamento das informações topológicas, sem causar impactos excessivos na velocidade de acesso às informações subjacentes. Esta estrutura é baseada em vértices, ou seja, as arestas e faces são representadas apenas de modo implícito. Antes de apresentarmos a estrutura em si, consideramos o problema de calcular transversais de triângulos mínimos, tanto por vértice, quanto por aresta. A complexidade computacional das versões de decisão associadas a estes problemas é demonstrada para o caso de grafos planares e maximais planares. Para os transversais por vértice, apresentamos também quatro algoritmos acompanhados de seus resultados experimentais. Demonstramos ainda dois teoremas sobre a complexidade do problema de vigilância em terrenos. Ao final, descrevemos a interface da estrutura implementada e sua utilização em um algoritmo de construção de triangulações de Delaunay. Os resultados demonstram que, em média, é possível reduzir em 12% o número de referências utilizadas, mantendo sua performance compatível com a de estruturas do mesmo tipo.
Abstract
The aim of this thesis is to design a data structure for representing planar triangulations decreasing the amount of redundancy of combinatorial data, without incurring excessive speedowns to the access of the underlying information. This structure is based on vertices in the sense that edges and faces are only implicitly represented. Before presenting our structure, we consider the problem of computing minimum triangle transversals using either vertices or edges. The computational complexity of the decision versions associated to these problems is demonstrated for the case of planar and maximal planar graphs. Regarding vertex-transversals, we present four algorithms along with experimental results. We also prove two theorems on the complexity of the guarding terrains problem. At last, we describe the interface of our data structure and its application for constructing Delaunay triangulations of planar point sets. Our results show that, on the average, it is possible to reduce in 12% the number of stored references, while maintaining its performance similar to the one of a standard vertex-based structure.
