not available

Problemas em geometria computacional permitem a modelagem de situações do mundo físico no computador, de forma que esses problemas possam ser resolvidos eficientemente. Estudamos algoritmos e estruturas de dados para a solução de problemas de geometria computacional no âmbito cinético, ou seja, onde admitimos que os objetos geométricos (pontos, retas, polígonos, etc.) possuam movimento associado. Com isso, nos problemas cinéticos o valor dos atributos geométricos, que são propriedades geométricas de um conjunto, se altera com o passar do tempo. Nesta dissertação abordamos, no cenário cinético, o problema de se manter o máximo de um conjunto, o par de pontos mais próximo, o fecho convexo e o diagrama de Voronoi. Esses são exemplos de atributos geométricos. Para que possamos manter atributos geométricos sobre um conjunto de objetos em movimento de forma eficiente, apresentamos um modelo proposto por Basch, Guibas e Hershberger, que introduz as estruturas de dados cinéticos. Elas são compostas de uma prova da corretude de atributo sendo 'animada' através do tempo. Apesar do movimento contínuo de cada objeto, o atributo somente será alterado pela ocorrência de eventos em momentos discretos no tempo. O modelo também introduz medidas para a análise do desempenho de tais estruturas sob quatro diferentes pontos de vista. Uma estrutura de dados cinética, segundo o modelo, deve ser eficiente, local, compacta e ter resposta rápida. Apresentamos também uma estratégia de implementação para as estruturas de dados cinéticas e exemplificamos sua utilização no problema do máximoComputational geoemtry problems allow modeling real world's situations in the computer as this problems can be solved efficiently. We studied algorithms and data structures to solution computational geometry problems at the kinetic scenario. In this kind of scenario, we allow the geoemtric objects (points, edges, polygons, etc.) have associated movement. Thus, in the kinetic problems, the value of geometric attributes change itself while the time advance. In this dissertation we approach, under the kinetic scenario, the problem of maintenance of the maximum element of a set, the closet pair of points, the convex hull and the Voronoi diagram. These are geometric attribute examples that mantain geometric attributes about a set of moving objects, we present a model proposed by Basch, Guibas and Hershberger, that introduce the kinetic data structures. They are composed by a proof of the correctness being 'animated' over the time. Although the continuous movement of each object, the attribute only will be changed by the occurrence of events in discrete instants. The model also introduce techniques to measure performance of these kinetic data structures under four different points of view. A kinetic data structure, under the model, must be efficient, local, compact and responsive. We also present a strategy for implement kinetic data structures. We exemplify the usability of this strategy at the problem of maintenance of the maximum element of a set of moving point