• 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-20220712-115327
Document
Author
Full name
Cassio Polpo de Campos
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2000
Supervisor
Title in Portuguese
Problemas dinâmicos em geometria computacional
Abstract in Portuguese
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
Title in English
not available
Abstract in English
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
 
Publishing Date
2022-07-13
 
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.