Esqueletos retilíneos de polígonos e poliedros

Abstract

Este trabalho é dedicado ao estudo dos esqueletos retilíneos de polígonos e poliedros. Os esqueletos retilíneos surgem por necessidade de criar estruturas que preservam a forma topológica dos objetos, usando um tamanho reduzido de informação. Começamos por abordar o conceito de esqueleto retilíneo de um polígono, estrutura unidimensional constituída por segmentos de reta, onde o processo de propagação de frente de onda vai permitir definir, de uma forma dinâmica, este conceito. Serão apresentadas propriedades relevantes acerca desta estrutura e ainda mencionadas aplicações dos esqueletos retilíneos, nomeadamente em telhados, ilhas e no problema da dobra e do corte. Em seguida passamos à construção de esqueletos retilíneos de poliedros que assenta também num processo dinâmico que permite encolher estes sólidos. A definição de esqueleto retilíneo para o caso tridimensional tem por base conceitos distintos dos que apresentamos no caso dos polígonos, tais como figura de vértice cónica e polígono esférico. Será apresentado um exemplo que ilustra a ambiguidade da definição de esqueleto retilíneo de poliedros. De modo a solucionar esta ambiguidade, introduzimos o conceito de esqueleto esférico e analisamos todos os eventos relacionados com o processo de construção desta estrutura. Fazemos ainda o levantamento de todos os eventos que podem ocorrer durante o processo de encolhimento de um poliedro, no caso genérico. Terminamos com alguns resultados relacionados com a combinatória dos esqueletos retilíneos de poliedros.

In this dissertation, we study straight skeletons of polygons and polyhedrons. The straight skeletons have appeared associated with the necessity of creating structures that preserve the topological form of objects and that at the same time use a reduced size of information. We start by introducing the concept of the straight skeleton of a polygon, which is a one-dimensional structure consisting only in straight segments and where the wavefront propagation process will allow us to define dynamically this concept. We introduce some of the most important properties of straight skeletons and we present three applications of this structure, namely in roofs, in islands and in the fold and one cut problem. We proceed to the study of the straight skeletons of polyhedrons. This concept is also based in a dynamical process that allows these solids to be shrunk. The definition of straight skeletons in the three-dimensional case is based on different concepts from those presented for the case of polygons. Therefore, we need to introduce concepts such as a vertex figure and a spherical polygon. It will be given one example that shows the ambiguity of the definition of straight skeletons of polyhedrons. In order to solve the problem of the non uniqueness of this definition, we introduce the concept of a spherical skeleton and we analyse the events related to the construction of this structure. A survey of all the events, that occur during the polyhedron shrinking process, in generic case, is presented. We finish with some combinatorial results about the straight skeleton of polyhedrons.