Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/14331
Document type: Tese
Access type: Acesso Aberto
Title: Uma proposta para a triangulação de Delaunay 2D e localização planar de pontos em OCaml
Author: Moura, Andre Luiz
First Advisor: Camacho, José Roberto
First member of the Committee: Pereira, Antônio Eduardo Costa
Second member of the Committee: Lamounier Júnior, Edgard Afonso
Third member of the Committee: Pérez, Mário Mourelle
Fourth member of the Committee: Mesquita, Renato Cardoso
Fifth member of the Committee: Guimarães Júnior, Sebastião Camargo
Summary: Nesta tese, é apresentado um algoritmo dinâmico de localização planar de pontos. O algoritmo foi elaborado sobre dois fundamentos: - o método das Slabs para particionar a subdivisão planar, representada por um grafo, e permitir a rápida identificação da região em que se encontra o ponto que está sendo consultado; - a Multiárvore-B Intervalar, uma estrutura de dados derivada árvore-B, aparelhada com mecanismo de pesquisa intervalar e disposta em camadas. O algoritmo é dinâmico porque altera dinamicamente a estrutura de pesquisa, à medida que surgem eventos de inserção ou remoção de segmentos na subdivisão planar que está sendo construída. O algoritmo foi implementado na linguagem OCaml, mas poderia ter sido implementado em qualquer outra linguagem de programação. Para aumentar a eficiência do algoritmo, algumas melhorias podem ser introduzidas, como por exemplo, a substituição do núcleo da Multiárvore-B Intervalar por outros tipos de árvores balanceadas. Adicionalmente, foram discutidos alguns aspectos do processso de construção de malhas de elementos finitos, em que se insere, sobretudo, o problema da localização planar de pontos.
Abstract: In this thesis, it is presented a planar point location algorithm. The algorithm was developed on top of two elements: - the method of slabs to divide the planar subdivision, is represented by a graph, allowing the fast identification of the region where the point being recalled is; - the Interval Multi-B-tree, a data structure derived from the B-tree, prepared with an interval search structure and disposed in layers. The algorithm is essentially dynamic since the search structure keeps changing dynamically during the process, while the planar subdivision is being built; new events of segment insertion or removal keep appearing. The algorithm was implemented in OCaml, but could be carried out in any other programming language. To increase the algorithm efficiency, some improvements can be introduced, as an example, the substitution of the Interval Multi-B-tree core by other types of balanced trees. Moreover, it was discussed some aspects of the assembling process of the finite element meshing, where it is inserted, mainly, the planar point location problem.
Keywords: Localização planar de pontos dinâmica
Árvore balanceada
Multiárvore-B intervalar
Triangulação de Delaunay incremental
Malha bidimensional
OCaml
Dynamic planar point location
Balanced tree
Interval multi-B-tree
Incremental Delaunay triangulation
Two dimensional meshing
Engenharia elétrica - Matemática
Area (s) of CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Language: por
Country: BR
Publisher: Universidade Federal de Uberlândia
Institution Acronym: UFU
Department: Engenharias
Program: Programa de Pós-graduação em Engenharia Elétrica
Quote: MOURA, Andre Luiz. Uma proposta para a triangulação de Delaunay 2D e localização planar de pontos em OCaml. 2006. 115 f. Tese (Doutorado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2006.
URI: https://repositorio.ufu.br/handle/123456789/14331
Date of defense: 30-Jun-2006
Appears in Collections:TESE - Engenharia Elétrica

Files in This Item:
File Description SizeFormat 
ALMouraTESPRT.pdf1.48 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.