Algoritmos para geracao da triangulacao de Delaunayatraves de Mudanca Global de Arestas e por

Insercao Incremental de Pontos

Jessica Renata Nogueira∗ Sanderson L. Gonzaga de OliveiraDepartamento de Ciencia da Computacao, DCC, UFLA,

37200-000, Lavras, MG

E-mail: jessica renata 1@hotmail.com, sanderson@dcc.ufla.br

RESUMO

Este trabalho tem por objetivo apresentar dois algoritmos que geram a triangulacao deDelaunay. A triangulacao de Delaunay foi proposta por Delaunay [3] e possui a propriedade demaximizacao do angulo mınimo de cada triangulo. Em disciplinas como geofısica e cristalografia,a utilizacao de uma malha composta por triangulos de qualidade podem levar a bons resultadosnos metodos que as utilizam. O uso de malhas de boa qualidade e importante na aplicacaoem metodos como metodo dos elementos finitos, das diferencas finitas e dos volumes finitos.No teste do circuncırculo, um triangulo e localmente Delaunay se nao contem nenhum outroponto interno a seu circuncırculo, alem de seus vertices. Uma triangulacao de Delaunay contemsomente triangulos localmente de Delaunay.

Os algoritmos que geram a triangulacao de Delaunay podem ser classificados como algo-ritmos por insercao incremental de pontos, por construcao incremental, algoritmos por divisaoe conquista, por mudanca global de arestas e algoritmos por gift-wrapping (ou embrulho parapresente). Neste trabalho, serao apresentados somente dois algoritmos, que sao o algoritmo deLawson e o algoritmo de Watson.

O algoritmo de Lawson [4] e tambem chamado de algoritmo de flip de arestas. Este algoritmoe classificado como algoritmo por mudanca global de arestas. No algoritmo de Lawson, se umtriangulo nao e Delaunay, realizam-se sucessivas trocas nas arestas que compoem a triangulacaoa fim de que, ao termino do algoritmo, haja uma triangulacao de Delaunay. Segundo Sloan [7],para que uma triangulacao transforme-se em uma triangulacao de Delaunay, e necessario umtempo de execucao, no pior caso e para n pontos, de O(n2). Na media dos casos, o algoritmo

de Lawson, segundo Sloan [7], ocorre em tempo O(n43 ).

Em geral, o algoritmo de Lawson e utilizado como um algoritmo auxiliar em algoritmosde insercao de novos pontos em uma triangulacao de Delaunay ja construıda. Isso porqueo algoritmo de Lawson pode ser utilizado para manter a triangulacao de Delaunay, apos asinsercoes de pontos. A ideia de realizar a troca nas arestas que compoem a triangulacao propostapor Lawson foi generalizada por Rajan [5] para dimensoes arbitrarias.

O segundo algoritmo apresentado e o algoritmo de Watson [8]. Esse e um algoritmo deinsercao de pontos. O algoritmo de Watson pode ser encontrado como algoritmo de Bowyer-Watson, pois Bowyer [2] propos um algoritmo semelhante ao proposto por Watson. Porem,o algoritmo de Bowyer pode ser aplicado ao diagrama de Voronoi, que e o dual geometricoda triangulacao de Delaunay. Sera descrito o algoritmo de Watson de maneira bidimensional.Entretanto, o algoritmo de Watson pode ser utilizado em dimensoes arbitrarias. O tempo de

∗bolsista de Iniciacao Cientıfica PIBIC/FAPEMIG.

413

ISSN 1984-8218

execucao desse algoritmo, para uma estrutura bidimensional e que contem n pontos e, segundoSloan [7], no pior caso, O(n2). Ja na media dos casos, o tempo de execucao do algoritmo de

Watson e, segundo Sloan [7], O(n32 ).

O passo inicial para a realizacao do algoritmo de Watson e a insercao de um ponto em umatriangulacao de Delaunay. Feito isso, verificam-se quais os triangulos em que seus circuncırculoscontem o ponto inserido. As arestas desses triangulos serao armazenadas. As arestas que foremarmazenadas duas vezes serao excluıdas da triangulacao de Delaunay atual e os vertices queformavam essas arestas sao ligadas ao vertice inserido.

Segundo Shewchuk [6], o algoritmo de Watson pode gerar uma triangulacao que nao sejaDelaunay. Isso porque o algoritmo de Watson nao e robusto em casos de arredondamento emque se utilizam operacoes com ponto flutuante. O erro de ponto flutuante, no algoritmo deWatson, pode ocorrer quando se deve decidir se o ponto e interior a um circuncırculo.

De acordo com Shewchuk [6], o algoritmo de Lawson, quando nao ocorrem erros de arredon-damento no algoritmo de Watson, gera a mesma malha que a gerada pelo algoritmo de Watson.Segundo Shewchuk [6], o algoritmo de Lawson tambem nao e totalmente robusto em relacao aerros de arredondamento. Porem, falhas sao raras no algoritmo de Lawson em comparacao asfalhas ocorridas utilizando-se o algoritmo de Watson.Palavras-chave: Triangulacao de Delaunay, algoritmo de Lawson, algoritmo de Watson

AGRADECIMENTOSAgradecemos a Fundacao de Amparo a Pesquisa do Estado de Minas Gerais – FAPEMIG

pelo apoio financeiro ao projeto de pesquisa em que este resultado esta vinculado.

Referencias

[1] T.B. Barth, “Aspects of unstructured grids and finite- volume solvers for the Euler andNavier-Stokes equations”, Von Karman Institute for Fluid Dynamics Lecture Series, NASAAmes Research Center, 1994-1995.

[2] A. Bowyer, Computing Dirichlet Tessellations, The Computer Journal, 24 (1981):2, 162-166.

[3] B.N. Delaunay, “Sur la sphere vide”, Izvestia Akademii Nauk SSSR, Otdelenie Matemati-cheskikh i Estestvennykh Nauk, 7 (1934) 793-800.

[4] C.L. Lawson, Software for C1 Surface Interpolation, em “Mathematical Software III” (J.Rice, ed.), pp. 161-194, Academic Press, New York, 1977.

[5] V.T. Rajan, Optimality of the Delaunay triangulation in Rd, em “Proceedings of the seventhannual symposium on Computational geometry, SCG ’91”, ACM, North Conway, NewHampshire, United States, pp. 357-363, 1991.

[6] J.R. Shewchuk, ”Delaunay Refinement Mesh Generation”, Tese de Doutorado, School ofComputer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, Available as Te-chnical Report CMU-CS-97-137, 1997.

[7] S.W. Sloan, A fast algorithm for constructing Delaunay triangulations in the plane, em“Advances in Engineering Software”, Oxford, UK, 9 (1987):1, 34–55.

[8] D.F. Watson, Computing the n-dimensional delaunay tessellation with application to voro-noi polytopes, The Computer Journal, 24 (1981):2, 167-172.

414

ISSN 1984-8218