Algoritmo de triangulación voraz

Algoritmo de Triangulación Voraz
Triangulación del interior de un polígono paso a paso mediante el algoritmo voraz que escoge la diagonal más corta.
Tipo	Algoritmo voraz
Problema que resuelve	Triangulación de un polígono
Estructura de datos	Cola de prioridades
Clase de complejidad	P
Tiempo de ejecución
Peor caso	${\displaystyle O(n\cdot \log n)}$
Mejor caso	${\displaystyle O(n)}$

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 ${\displaystyle O(N^{2})}$ para un conjunto de entrada de ${\displaystyle N}$ puntos.[3]​
• Existen implementaciones capaces de calcular la triangulación voraz en tiempo ${\displaystyle O(n\cdot \log n)}$ 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:

Algoritmo triangulación voraz

1 Crear un solución inicial con las aristas del polígono de entrada (o vacía, en caso de nubes de puntos) 2 Crear una lista de aristas candidatas, combinando todos los vértices de entrada dos a dos. 3 Ordenar la lista de candidatas anterior de menor a mayor longitud de arista. 4 Mientras la lista de candidatas no sea vacía. 4.1 Obtener la primera arista de la lista (la más corta) y borrarla de la lista de candidatas. 4.2 Si la arista candidata no se cruza con ninguna otra de la triangulación, insertarla en la triangulación.

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 ${\displaystyle n^{2}}$. Para ello debería emplearse alguna versión eficiente del Problema del par de puntos más cercanos (que puede resolverse en tiempo ${\displaystyle n\cdot \log n}$),[5]​[6]​ o bien emplear una triangulación de Delaunay como paso intermedio.[4]​

Referencias

1. Loera, Jesús A.; Rambau, Joerg; Santos, Francisco (2010). Triangulations: Structures and Algorithms. (en inglés). Springer Science & Business Media. pp. 103. ISBN 9783642129711. Consultado el 21 de febrero de 2017. (requiere registro). 
2. Dickerson, Matthew T. (1997). «Fast greedy triangulation algorithms». Computational Geometry (Elsevier) 8 (2): 67-86. Consultado el 21 de febrero de 2017. 
3. Debido a que existen ${\displaystyle N*(N-1) \over 2}$ aristas candidatas iniciales, que deben ser comprobadas.
4. Levcopoulos, Christos (1999). «The greedy triangulation can be computed from the Delaunay triangulation in linear time». Computational Geometry (Elsevier) 14 (4): 197-220. Consultado el 21 de febrero 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

• Datos: Q28811699
• Multimedia: Greedy Triangulation / Q28811699