CITI has stopped operations in 2014, to co-launch NOVA LINCS THIS SITE IS NOT BEING UPDATED SINCE 2013
citi banner
Home Page FCT/UNL UNL
  Home  \  Graduation Activities  \  Post-Graduation Page Login  
   
banner bottom
File Top
Construção e Edição de Diagramas de Voronoi na Esfera
Phd Post-Graduation
Abstract:

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.


Start Date: 2008-04-11

End Date: 2013-11-27




Post-Graduation Student / Researcher / Professor:
  • João Carlos de Brito Dinis ( Instituto Nacional de Engenharia Tecnologia e Inovação )

Post-Graduation Supervisor(s):

Post-Graduation Jury:
File Bottom