Algoritme de triangulació voraç

El Algoritme de Triangulació Voraç és un método per a calcular una triangulació d'un polígon o d'un núvol de punts per mig d'un método voraç, que consistix en afegir arestes a la solució d'una en una unint el parell de vèrtiços més pròxims entre sí, en la condició de que una nova aresta no pot tallar a una atra prèviament afegida al resultat. ^[1]^[2]

Propietats

Les triangulacions calculades per mig de l'algoritme de triangulació voraç tenen les següents propietats:

Són una bona aproximació de la triangulació de pes mínim d'un polígon o núvol de punts, encara que no sempre coincidixen.
Freqüentment, encara que no sempre, solen coincidir en la triangulació de Delaunay de les mateixes senyes d'entrada.
Si l'entrada és un núvol de punts, totes les arestes del tancament convexo pertanyen a la triangulació voraç.
Si l'entrada és un polígon, les arestes de la triangulació són un subconjunt de les diagonalés internes del polígon.
L'implementació per força bruta de l'algoritme és d'orde $O (N^{2})$ per a un conjunt d'entrada de $N$ punts.^[3]
Existixen implementacions capaces de calcular la triangulació voraç en temps $O (n \cdot \log n)$ amprant estructures adicionals per a comprovar els creus entre arestes.^[2]
La triangulació voraç pot calcular-se a partir de la triangulació de Delaunay afegint una cantitat de temps llineal.^[4]

Pseudoalgoritmo

Existixen vàries possibles estratègies per a implementar l'algoritme de triangulació voraç. Tal volta, la més senzilla de totes siga la següent:

No obstant, existixen solucions alternatives que poden accelerar molt la construcció en cas que l'entrada tinga un tamany considerable.^[2] Especialment si el número de vèrtiços en l'entrada és gran, es deuria evitar la comparació de tots els vèrtiços d'entrada dos a dos, ya que és un problema d'orde $n^{2}$ . Per a això deuria amprar-se alguna versió eficient del Problema del parell de punts més propencs (que pot resoldre's en temps $n \cdot \log n$ ),^[5]^[6] o be amprar una triangulació de Delaunay com a pas intermig.^[4]

Referències

↑ Loera, Jesús A.; Rambau, {{{nom2}}} (2010). Triangulations: Structures and Algorithms. (en anglés), Springer Science & Business Mija, pp. 103. ISBN 9783642129711.
↑ ^2,0 ^2,1 ^2,2 (1997).Computational Geometry.Elsevier.8(2)
67-86.Consultat el 21 de febrer de 2017.
↑ Degut a que existixen $\frac{N * (N - 1)}{2}$ arestes candidates inicials, que deuen ser comprovades.
↑ ^4,0 ^4,1 (1999).Computational Geometry.Elsevier.14(4)
197-220.Consultat el 21 de febrer de 2017.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 957–961 of section 33.4: Finding the closest pair of points.
↑ UCSB Lecture Notes

Referències

Este artícul conté una traducció derivada de «Algoritmo de triangulación voraz» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Loera2010-1] Loera, Jesús A.; Rambau, {{{nom2}}} (2010). Triangulations: Structures and Algorithms. (en anglés), Springer Science & Business Mija, pp. 103. ISBN 9783642129711.

[Dickerson1997-2] 2,0 ^2,1 ^2,2 (1997).Computational Geometry.Elsevier.8(2)
67-86.Consultat el 21 de febrer de 2017.

[3] Degut a que existixen $\frac{N * (N - 1)}{2}$ arestes candidates inicials, que deuen ser comprovades.

[Levcopoulos-4] 4,0 ^4,1 (1999).Computational Geometry.Elsevier.14(4)
197-220.Consultat el 21 de febrer de 2017.

[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 957–961 of section 33.4: Finding the closest pair of points.

[6] UCSB Lecture Notes

[1]

[2]

[3]

[4]

[5]

[6]