A carregar...
Publicação
Construção e edição de diagramas de Voronoi na esfera
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 8.42 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Muitos objectos de estudo em ciências da Terra e do Espaço são representados por pontos na superfície de uma esfera, identificando, por exemplo, medidas de temperatura nos oceanos ou posições de estrelas na esfera celeste. Nestes contextos, o diagrama de Voronoi esférico é a ferramenta natural para o processamento e a análise de relações de proximidade entre os pontos.
Presentemente, o diagrama de Voronoi esférico pode ser obtido por uma de duas
formas: construindo o invólucro-convexo tridimensional dos pontos na superfície da
esfera ou adaptando à esfera o algoritmo incremental de construção da triangulação
de Delaunay no plano. Porém, os algoritmos usados na prática possuem uma complexidade
temporal quadrática, no pior caso, e os que calculam o invólucro-convexo são susceptíveis de produzir um resultado errado, ao não incluir todos os pontos na
estrutura construída.
Como alternativa, é proposta uma adaptação ao domínio esférico do algoritmo de construção do diagrama de Voronoi planar pelo método do varrimento. O novo algoritmo constrói um diagrama em tempo O.n log n/, onde n é o número de pontos,o que é óptimo no pior caso. Adicionalmente, são propostos dois algoritmos de edição de diagramas de Voronoi esféricos, um de inserção e outro de remoção de um ponto, igualmente baseados no método do varrimento. Em conjunto, os novos
algoritmos implementam uma estrutura de dados dinâmica, apropriada para cenários
em que a informação é variável no tempo.
Mostra-se que, para além de eficientes, os três algoritmos são fáceis de implementar
e robustos a configurações de pontos degeneradas. Estas propriedades são
verificadas experimentalmente, com dados sintéticos e reais. A aplicabilidade dos
algoritmos desenvolvidos é ainda exemplificada através de um problema de redução de um catálogo de estrelas.
Descrição
Dissertação para obtenção do Grau de Doutor em
Informática
Palavras-chave
Diagramas de Voronoi esféricos Edição de diagramas de Voronoi Técnica do varrimento do plano Geometria computacional Processamento de catálogos de estrelas