Algoritmo de triangulación voraz
El Algoritmo de Triangulación Voraz es un método para calcular una triangulación de un polígono o de una nube de puntos mediante un método voraz, que consiste en añadir aristas a la solución de una en una uniendo el par de vértices más próximos entre sí, con la condición de que una nueva arista no puede cortar a otra previamente añadida al resultado. [1][2]
Propiedades
Las triangulaciones calculadas mediante el algoritmo de triangulación voraz tienen las siguientes propiedades:
- Son una buena aproximación de la triangulación de peso mínimo de un polígono o nube de puntos, aunque no siempre coinciden.
- Frecuentemente, aunque no siempre, suelen coincidir con la triangulación de Delaunay de los mismos datos de entrada.
- Si la entrada es una nube de puntos, todas las aristas del cierre convexo pertenecen a la triangulación voraz.
- Si la entrada es un polígono, las aristas de la triangulación son un subconjunto de las diagonales internas del polígono.
- La implementación por fuerza bruta del algoritmo es de orden para un conjunto de entrada de puntos.[3]
- Existen implementaciones capaces de calcular la triangulación voraz en tiempo empleando estructuras adicionales para comprobar los cruces entre aristas.[2]
- La triangulación voraz puede calcularse a partir de la triangulación de Delaunay añadiendo una cantidad de tiempo lineal.[4]
Pseudoalgoritmo
Existen varias posibles estrategias para implementar el algoritmo de triangulación voraz. Tal vez, la más sencilla de todas sea la siguiente:
Sin embargo, existen soluciones alternativas que pueden acelerar mucho la construcción en caso de que la entrada tenga un tamaño considerable.[2] Especialmente si el número de vértices en la entrada es grande, se debería evitar la comparación de todos los vértices de entrada dos a dos, ya que es un problema de orden . Para ello debería emplearse alguna versión eficiente del Problema del par de puntos más cercanos (que puede resolverse en tiempo ),[5][6] o bien emplear una triangulación de Delaunay como paso intermedio.[4]
Referencias
Plantilla:Control de autoridades
- ↑ Plantilla:Cita libro
- ↑ 2,0 2,1 2,2 Plantilla:Cita publicación
- ↑ Debido a que existen aristas candidatas iniciales, que deben ser comprobadas.
- ↑ 4,0 4,1 Plantilla:Cita publicación
- ↑ 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