Uma Visão Geral sobre Técnicas para Construção de Algoritmos para a Geração da Tesselação de Delaunay e do Diagrama de Voronoi

Resumo

Neste trabalho, são abordadas, resumidamente, as técnicas utilizadas no projeto de algoritmos para a geração da tesselação de Delaunay ou do diagrama de Voronoi. Essas malhas possuem aplicações em áreas diversas, em que computação científica, visualização e sistemas de informações geográficas são exemplos. Várias técnicas já foram utilizadas na construção de algoritmos para a geração da tesselação de Delaunay e do diagrama de Voronoi. Escolher a técnica mais adequada pode permitir a criação de algoritmos eficientes em tempo de execução, na utilização de memória, que facilitem a implementação e/ou o paralelismo, entre outras vantagens. Neste trabalho são descritas as abordagens por divisão e conquista, inserção incremental, mudança global de arestas, por linha de varredura (sweepline), por lifting map, por gift wrapping e a técnica de varredura por círculo.