Use este identificador para citar ou linkar para este item: repositorio.ufla.br/jspui/handle/1/10427
Título: Uma avaliação de sequências de inserção em algoritmos incrementais para a tesselação de Delaunay
Título(s) alternativo(s): An evaluation of insertion sequences in incremental algorithms for Delaunay tessellation
Autor : Nogueira, Jéssica Renata
Lattes: http://lattes.cnpq.br/1629259956786520
Primeiro orientador: Oliveira, Sanderson Lincohn Gonzaga de
Primeiro membro da banca: Alves Filho, Hermes
Segundo membro da banca: Vasconcellos, João Flávio Vieira de
Palavras-chave: 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
Data da publicação: 25-Set-2015
Agência(s) de fomento: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Referência: NOGUEIRA, J. R. Uma avaliação de sequências de inserção em algoritmos incrementais para a tesselação de Delaunay. 2015. 119 p. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Lavras, Lavras, 2015.
Resumo: Neste trabalho, são avaliadas 8 sequências de inserção de pontos em algoritmos incrementais para a geração da tesselação de Delaunay. Quatro dessas sequências são consideradas pela primeira vez: H-Indexing, espiral, rubro-negra em ordem e rubro-negra em largura. Essas sequências foram comparadas com: a sequência de inserção de pontos pela cut-longest-edge kd-tree; com a sequência dada pela curva de Hilbert; com a curva de Lebesgue; e também com sequência dada por inserção aleatória de pontos. Ao utilizar a biblioteca MPFR, foram testadas 6 distribuições de pontos no quadrado unitário e 7 distribuições de pontos no cubo unitário. Os algoritmos incrementais com as 4 sequências propostas neste trabalho não se mostraram competitivos com o algoritmo incremental com inserção de pontos dada pela cut-longest-edge kd-tree. Mais especificamente, o algoritmo incremental com inserção de pontos dada pela ordem da cut-longest-edge kd-tree apresentou os menores custos computacionais na geração das malhas, em todas as distribuições de pontos, em testes realizados em estruturas bidimensionais e tridimensionais.
Abstract: 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.
URI: http://repositorio.ufla.br/jspui/handle/1/10427
Publicador: Universidade Federal de Lavras
Idioma: por
Aparece nas coleções:DCC - Ciência da Computação - Mestrado (Dissertações)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DISSERTACAO_Uma avaliação de sequências de inserção em algoritmos....pdf1,85 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.