Uma avaliação de sequências de inserção em algoritmos incrementais para a tesselação de Delaunay

• Ano de defesa: 2015
• Autor(a) principal: Nogueira, Jéssica Renata
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Lavras; Programa de Pós-Graduação em Ciência da Computação; UFLA; brasil; Departamento de Ciência da Computação
• Palavras-chave em Português: Geração de malha; Mesh generation; Delaunay tessellation; Geometria computacional; Computational geometry; Algoritmos incrementais; Incremental algorithms; Insertion sequences; Distribuição não uniforme de pontos; Ciência da Computação
• Link de acesso: http://repositorio.ufla.br/jspui/handle/1/10427

In this work, it is evaluated 8 insertion-point sequences in incremental algorithms to generate the Delaunay tessellation. Four of these sequences are considered for the first time: H-Indexing, spiral, red-black tree in-order and red-black-tree in level-order traversal. These sequences are compared with: point-insertion order given by cut-longest-edge kd-tree; with the order given by Hilbert space-filling curve; with Lebesgue space- filling curve and with the random point-insertion order. Using the GNU MPFR library, 6 dataset distributions were tested on unit square and 7 dataset distributions on the unit cube. The incremental algorithms with the 4 sequences that were proposed in this work are not competitive with the incremental algorithm using the point-insertion given by cut-longest-edge kd-tree. More specifically, the incremental algorithm using point-insertion sequence in the order given by the cut-longest-edge kd-tree, shows the lowest computational cost on mesh generation in tests carried out on 2D and on 3D.