Algoritmo de triangulación voraz

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]

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 ${\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]