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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOliveira, Sanderson Lincohn Gonzaga de-
Autor(es): dc.contributorAlves Filho, Hermes-
Autor(es): dc.contributorVasconcellos, João Flávio Vieira de-
Autor(es): dc.creatorNogueira, Jéssica Renata-
Data de aceite: dc.date.accessioned2026-02-09T11:17:37Z-
Data de disponibilização: dc.date.available2026-02-09T11:17:37Z-
Data de envio: dc.date.issued2015-09-25-
Data de envio: dc.date.issued2015-09-25-
Data de envio: dc.date.issued2015-09-25-
Data de envio: dc.date.issued2015-07-17-
Fonte completa do material: dc.identifierhttps://repositorio.ufla.br/handle/1/10427-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1137765-
Descrição: dc.descriptionIn 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.-
Descrição: dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)-
Descrição: dc.descriptionNeste 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Federal de Lavras-
Publicador: dc.publisherPrograma de Pós-Graduação em Ciência da Computação-
Publicador: dc.publisherUFLA-
Publicador: dc.publisherbrasil-
Publicador: dc.publisherDepartamento de Ciência da Computação-
Direitos: dc.rightsacesso aberto-
Palavras-chave: dc.subjectGeração de malha-
Palavras-chave: dc.subjectMesh generation-
Palavras-chave: dc.subjectDelaunay tessellation-
Palavras-chave: dc.subjectGeometria computacional-
Palavras-chave: dc.subjectComputational geometry-
Palavras-chave: dc.subjectAlgoritmos incrementais-
Palavras-chave: dc.subjectIncremental algorithms-
Palavras-chave: dc.subjectInsertion sequences-
Palavras-chave: dc.subjectDistribuição não uniforme de pontos-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleUma avaliação de sequências de inserção em algoritmos incrementais para a tesselação de Delaunay-
Título: dc.titleAn evaluation of insertion sequences in incremental algorithms for Delaunay tessellation-
Tipo de arquivo: dc.typedissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal de Lavras (RIUFLA)

Não existem arquivos associados a este item.