Buscar

 

RI UFLA (Universidade Federal de Lavras) >
DCC - Departamento de Ciência da Computação >
DCC - Programa de Pós-graduação >
DCC - Ciência da Computação - Mestrado (Dissertações) >

Por favor, utilize esse identificador para citar este item ou usar como link: http://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 Alternativo: An evaluation of insertion sequences in incremental algorithms for Delaunay tessellation
Autor(es): Nogueira, Jéssica Renata
Lattes: http://lattes.cnpq.br/1629259956786520
Orientador: Oliveira, Sanderson Lincohn Gonzaga de
Membro da banca: Alves Filho, Hermes
Membro da banca: Vasconcellos, João Flávio Vieira de
Assunto: 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 de Defesa: 17-Jul-2015
Data de publicação: 25-Set-2015
Agência 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 neste Item:

Arquivo Descrição TamanhoFormato
DISSERTACAO_Uma avaliação de sequências de inserção em algoritmos....pdf1,85 MBAdobe PDFVer/abrir

Itens protegidos por copyright, com todos os direitos reservados, Salvo indicação em contrário.


Mostrar estatísticas

 


DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback