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.

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 $O(N^2)$ para un conjunto de entrada de $N$ puntos.
• Existen implementaciones capaces de calcular la triangulación voraz en tiempo $O(n\cdot \log n)$ empleando estructuras adicionales para comprobar los cruces entre aristas.
• La triangulación voraz puede calcularse a partir de la triangulación de Delaunay añadiendo una cantidad de tiempo lineal.

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. 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 $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 $n\cdot \log n$), o bien emplear una triangulación de Delaunay como paso intermedio.