Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/14331
metadata.dc.type: Tese
metadata.dc.rights: Acesso Aberto
Title: Uma proposta para a triangulação de Delaunay 2D e localização planar de pontos em OCaml
metadata.dc.creator: Moura, Andre Luiz
metadata.dc.contributor.advisor1: Camacho, Jose Roberto
metadata.dc.contributor.referee1: Pereira, Antônio Eduardo Costa
metadata.dc.contributor.referee2: Lamounier Júnior, Edgard Afonso
metadata.dc.contributor.referee3: Pérez, Mário Mourelle
metadata.dc.contributor.referee4: Mesquita, Renato Cardoso
metadata.dc.contributor.referee5: Guimarães Júnior, Sebastião Camargo
metadata.dc.description.resumo: 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
metadata.dc.subject.cnpq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
metadata.dc.language: por
metadata.dc.publisher.country: BR
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.initials: UFU
metadata.dc.publisher.department: Engenharias
metadata.dc.publisher.program: Programa de Pós-graduação em Engenharia Elétrica
Citation: 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
Issue Date: 30-Jun-2006
Appears in Collections:TESE - Engenharia Elétrica

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


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