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

Abstract

This paper overviews the techniques used for the design of algorithms for the generation of the Delaunay tessellation and Voronoi diagram. These meshes have applications in several areas, where scientific computing, scientific visualization, and geographic information systems are examples. Practitioners have been using several techniques in the construction of algorithms for the generation of the Delaunay tessellation and Voronoi diagram. Choosing the most appropriate technique can allow the creation of low-cost algorithms (in time and space) that facilitate implementation and parallelism, among other advantages. This paper considers the following techniques: divide and conquer, incremental algorithms, the Lawson flip algorithm, sweep-line algorithms, lifting map, gift wrapping, and sweep-circle algorithms.