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 para un conjunto de entrada de puntos.Debido a que existen aristas candidatas iniciales, que deben ser comprobadas. Existen implementaciones capaces de calcular la triangulación voraz en tiempo 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 . Para ello debería emplearse alguna versión eficiente del Problema del par de puntos más cercanos (que puede resolverse en tiempo ),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 o bien emplear una triangulación de Delaunay como paso intermedio.
Referencias
Triangulacion Voraz Voraz Categoría:Triangulación (geometría)