• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2000.tde-20210729-122556
Document
Auteur
Nom complet
Eduardo Garcia de Freitas
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2000
Directeur
Titre en portugais
Problemas cinéticos em geometria computacional
Mots-clés en portugais
Algoritmos E Estruturas De Dados
Geometria Computacional
Resumé en portugais
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
Titre en anglais
not available
Resumé en anglais
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
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.