Triangulación de polígonos

Es trivial triangular cualquier polígono convexo en tiempo lineal para obtener una triangulación en abanico , añadiendo diagonales desde un vértice a todos los demás vértices que no son vecinos más cercanos.

El número total de formas de triangular un n- gono convexo mediante diagonales que no se intersecan es el ( n -2)-ésimo número de Catalan , que es igual a

${\displaystyle {\frac {n(n+1)...(2n-4)}{(n-2)!}}}$,

una fórmula hallada por Leonhard Euler . ^{[ 2 ]}

Una forma de triangular un polígono simple se basa en el teorema de las dos orejas , que establece que cualquier polígono simple con al menos 4 vértices sin agujeros tiene al menos dos " orejas ", que son triángulos cuyos dos lados son los bordes del polígono y el tercero está completamente dentro de él. ^{[ 3 ]} El algoritmo consiste entonces en encontrar una de estas orejas, eliminarla del polígono (lo que da como resultado un nuevo polígono que aún cumple las condiciones) y repetir el proceso hasta que solo quede un triángulo.

Este algoritmo es fácil de implementar, pero más lento que otros, y solo funciona en polígonos sin agujeros. Una implementación que mantenga listas separadas de vértices convexos y cóncavos se ejecutará en tiempo O( n² ⁾ . Este método se conoce como recorte de orejas y, a veces, recorte de orejas . Hossam ElGindy, Hazel Everett y Godfried Toussaint descubrieron un algoritmo eficiente para recortar orejas . ^{[ 4 ]}

Un polígono simple es monótono con respecto a una línea L si cualquier línea ortogonal a L interseca el polígono como máximo dos veces. Un polígono monótono se puede dividir en dos cadenas monótonas . Un polígono que es monótono con respecto al eje y se llama y-monótono . Un polígono monótono con n vértices se puede triangular en tiempo O( n ) . Suponiendo que un polígono dado es y-monótono, el algoritmo voraz comienza recorriendo una cadena del polígono de arriba a abajo mientras agrega diagonales siempre que sea posible. ^{[ 1 ]} Es fácil ver que el algoritmo se puede aplicar a cualquier polígono monótono.

Un polígono monótono puede triangularse en tiempo lineal con el algoritmo de A. Fournier y DY Montuno, ^{[ 5 ]} o con el algoritmo de Godfried Toussaint . ^{[ 6 ]}

Si un polígono no es monótono, se puede particionar en subpolígonos monótonos en tiempo O( n log n ) utilizando un método de barrido lineal . El algoritmo no requiere que el polígono sea simple, por lo que se puede aplicar a polígonos con agujeros . En general, este algoritmo puede triangular una subdivisión plana con n vértices en tiempo O( n log n ) utilizando espacio O( n ) . ^{[ 1 ]}

Un grafo útil que suele asociarse a la triangulación de un polígono P es el grafo dual . Dada una triangulación T _P de P , se define el grafo G ( T _P ) como aquel cuyos vértices son los triángulos de T _P , siendo dos vértices (triángulos) adyacentes si y solo si comparten una diagonal. Es fácil observar que G ( T _P ) es un árbol con grado máximo 3.

Hasta 1988, la triangulación de un polígono simple en un tiempo inferior a O( n log n ) era un problema abierto en geometría computacional. ^{[ 1 ]} Luego, Tarjan y Van Wyk (1988) descubrieron un algoritmo de triangulación con un tiempo de O( n log log n ) , ^{[ 7 ]} posteriormente simplificado por Kirkpatrick, Klawe y Tarjan (1992) . ^{[ 8 ]} Posteriormente surgieron varios métodos mejorados con una complejidad de O( n log ^* n ) (en la práctica, indistinguible del tiempo lineal ). ^{[ 9 ] [ 10 ] [ 11 ]}

Bernard Chazelle demostró en 1991 que cualquier polígono simple puede triangularse en tiempo lineal, aunque el algoritmo propuesto es muy complejo. ^{[ 12 ]} También se conoce un algoritmo aleatorio más simple con tiempo esperado lineal. ^{[ 13 ]}

El algoritmo de descomposición de Seidel ^{[ 10 ]} y el método de triangulación de Chazelle se discuten en detalle en Li y Klette (2011) . ^{[ 14 ]}

La complejidad temporal de la triangulación de un polígono de n vértices con agujeros tiene una cota inferior de Ω( n log n ) en los modelos de árbol de computación algebraica. ^{[ 1 ]} Es posible calcular el número de triangulaciones distintas de un polígono simple en tiempo polinomial usando programación dinámica y (basándose en este algoritmo de conteo) generar triangulaciones aleatorias uniformes en tiempo polinomial. ^{[ 15 ]} Sin embargo, contar las triangulaciones de un polígono con agujeros es #P-completo , lo que hace improbable que se pueda hacer en tiempo polinomial. ^{[ 16 ]}