• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2000.tde-20210729-122556
Document
Author
Full name
Eduardo Garcia de Freitas
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2000
Supervisor
Title in Portuguese
Problemas cinéticos em geometria computacional
Keywords in Portuguese
Algoritmos E Estruturas De Dados
Geometria Computacional
Abstract in Portuguese
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áximo
Title in English
not available
Abstract in English
Computational 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 points
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2021-07-29
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.