• 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-20220712-115327
Document
Auteur
Nom complet
Cassio Polpo de Campos
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2000
Directeur
Titre en portugais
Problemas dinâmicos em geometria computacional
Mots-clés en portugais
Algoritmos E Estruturas De Dados
Geometria Computacional
Resumé en portugais
Nesta dissetação tratamos de geometria computacional no cenário dinâmico. Neste contexto, desejamos manter estruturas de dados que permitam que um determinado atributo geométrico possa ser calculado a qualquer instante, com o conjunto de dados sendo alterado por inserções e remoções. estudamos quatro problemas clássicos de geometria computacional no cenário dinâmico: busca por regiões, localização de pontos, fecho convexo e par de pontos mais próximos. Nossa abordagem é principalmente teórica, mostrando estruturas de dados dinâmicas que permitem que inserções, remoções e consultas sobre os atributos geométricos sejam feitas eficientemente. Tipicamente esperamos que tais operações sejam feitas em tempo polilogarítmico no tamanho da entrada. Apresentamos também implementações de alguns dos algoritmos e estruturas de dados tratadas para o problema da busca por regiões e o problema do fecho convexo
Titre en anglais
not available
Resumé en anglais
This work handles computational geometry problems in their dinamic versions. In this context, we want to mantain data structures supporting queries about geometric attributes at any time, with the data set being updated by insertions and delections of objects. We studied four classic problems of computational geometry in the dinamic scenario: range searching, point location, convex hull and the closest pair points. Our approach is mainly theoretical, showing dinamic data structues supporting insertions., delections and queries about geometric atributes efficiently. Tipically we expect these operations to be executed in polylogarithmic time on the size of the set. We present implementations for some algorithms and data structures in the range searching problem and the convex hull problem addressed in this dissertation
 
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.
CamposCassioPolpo.pdf (14.01 Mbytes)
Date de Publication
2022-07-13
 
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-2024. Tous droits réservés.