Construção e edição de diagramas de Voronoi na esfera

Dissertação para obtenção do Grau de Doutor em Informática

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.