Busca avançada
Ano de início
Entree


Problemas dinâmicos em geometria computacional

Texto completo
Autor(es):
Cassio Polpo de Campos
Número total de Autores: 1
Tipo de documento: Dissertação de Mestrado
Imprenta: São Paulo.
Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
Data de defesa:
Orientador: Carlos Eduardo Ferreira
Resumo

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 (AU)

Processo FAPESP: 98/16274-0 - Problemas dinamicos em geometria computacional.
Beneficiário:Cassio Polpo de Campos
Modalidade de apoio: Bolsas no Brasil - Mestrado