Problema de triangulación de polígonos

El problema de triangular un polígono  es un problema clásico de geometría combinatoria y computacional , que consiste en encontrar una triangulación de un polígono sin vértices adicionales.

La prueba de la existencia de tal triangulación no es difícil. Además, este problema siempre tiene solución para polígonos con agujeros, es decir, áreas del plano limitadas por varias líneas discontinuas cerradas.

Redacción

El problema es encontrar el algoritmo óptimo para triangular un n - gon sin vértices adicionales.

Este problema se puede resolver en tiempo lineal , es decir, el problema tiene complejidad .

Historia

Durante mucho tiempo estuvo abierta la pregunta de si es posible encontrar la triangulación de un n-ágono en un tiempo menor que . [1] Van Wyck (1988) luego descubrió un algoritmo que requería tiempo , [2] más tarde simplificado por Kirkpatrick y Clave. [3] Esto fue seguido por varios algoritmos con complejidad (donde es el logaritmo iterado de ) que son indistinguibles en la práctica del tiempo lineal . [4] [5] [6]

En 1991, Bernard Chazelle demostró que cualquier polígono simple se puede triangular en tiempo lineal, aunque el algoritmo que propuso resultó ser muy complicado. [7] También se conoce un algoritmo probabilístico más simple con tiempo esperado lineal. [8] [9]

Algoritmos

Corte de orejas

El gráfico de triangulación dual sin vértices adicionales de un polígono simple es siempre un árbol . Se sigue en particular que cualquier n -ágono simple con n > 3 tiene al menos dos orejas , es decir, dos triángulos, dos lados de cada uno de los cuales son lados del polígono, y el tercero está completamente dentro de él. [diez]

Una forma de triangular es encontrar esa oreja y cortarla del polígono. Después de eso, se repite la misma operación en el polígono restante hasta que quede un triángulo.

Este método solo funciona para polígonos sin agujeros. Es simple de implementar pero más lento que algunos otros algoritmos. Una implementación que mantiene listas separadas de vértices convexos y cóncavos se ejecuta en el tiempo .

Hossam El-Gindi, Hazel Everett y Godfried Toussaint propusieron un algoritmo eficiente para cortar las orejas. [once]

A través de polígonos monótonos

Un polígono se llama monótono si su polígono límite tiene como máximo dos puntos de intersección con una línea perpendicular a la dada.

Un polígono monótono se puede triangular en tiempo lineal utilizando el algoritmo de A. Fournier y D. Yu. Montuno [12] o el algoritmo de Godfried Toussaint. [13]

Un polígono arbitrario se puede subdividir en monótonos. Un algoritmo simple de triangulación de polígonos basado en esta idea se ejecuta en el tiempo .

Variaciones y generalizaciones

Véase también

Notas

  1. ↑ Mark de Berg, Marc van Kreveld, Mark Overmars y Otfried Schwarzkopf (2000), Computational Geometry (2.ª edición revisada), Springer-Verlag , ISBN 3-540-65620-0 
  2. ↑ Tarjan, Robert E. & Van Wyk, Christopher J. (1988), Un algoritmo de tiempo O( n log log n ) para triangular un polígono simple , SIAM Journal on Computing Vol. 17(1): 143–178 , DOI 10.1137/0217010  .
  3. ↑ Kirkpatrick, David G.; Klawe, Maria M. & Tarjan, Robert E. (1992), Triangulación de polígonos en tiempo O( n log log n ) con estructuras de datos simples , Geometría computacional y discreta Vol. 7 (4): 329–346 , DOI 10.1007/BF02187846  .
  4. ↑ Clarkson, Kenneth L.; Tarjan, Robert & van Wyk, Christopher J. (1989), Un algoritmo rápido de Las Vegas para la triangulación de un polígono simple , Geometría computacional y discreta Vol. 4: 423–432 , DOI 10.1007/BF02187741  .
  5. ↑ Seidel, Raimund (1991), Un algoritmo aleatorio incremental simple y rápido para calcular descomposiciones trapezoidales y triangular polígonos , Geometría computacional: teoría y aplicaciones Vol. 1: 51–64 , DOI 10.1016/0925-7721(91)90012-4 
  6. ↑ Clarkson, Kenneth L.; Cole, Richard & Tarjan, Robert E. (1992), Algoritmos paralelos aleatorios para diagramas trapezoidales , International Journal of Computational Geometry & Applications Vol. 2 (2): 117–133 , DOI 10.1142/S0218195992000081  .
  7. ↑ Chazelle, Bernard (1991), Triangulación de un polígono simple en tiempo lineal , Geometría computacional y discreta Vol. 6: 485–524, ISSN 0179-5376 , DOI 10.1007/BF02574703 
  8. ↑ Amato, Nancy M.; Goodrich, Michael T. & Ramos, Edgar A. (2001), Un algoritmo aleatorio para triangular un polígono simple en tiempo lineal , Geometría discreta y computacional Vol. 26 (2): 245–265, ISSN 0179-5376 , doi : 10.1007 /s00454-001-0027-x , < http://parasol.tamu.edu/publications/abstract.php?pub_id=185 > Archivado el 23 de julio de 2018 en Wayback Machine . 
  9. ↑ Li, Fajie & Klette, Reinhard (2011), Euclidean Shortest Paths , Springer , ISBN 978-1-4471-2255-5 , DOI 10.1007/978-1-4471-2256-2  .
  10. ↑ Meisters, GH, "Los polígonos tienen oídos".
  11. ↑ ElGindy, H.; Everett, H.; Toussaint, GT Cortar una oreja usando podar y buscar  // Letras de reconocimiento  de patrones : diario. - 1993. - vol. 14 , núm. 9 _ - Pág. 719-722 . -doi : 10.1016 / 0167-8655(93)90141-y .
  12. ↑ Fournier, A. & Montuno, DY (1984), Triangulación de polígonos simples y problemas equivalentes , ACM Transactions on Graphics Vol. 3 (2): 153–174, ISSN 0730-0301 , DOI 10.1145/357337.357341 
  13. ↑ Toussaint, Godfried T. (1984), "Un nuevo algoritmo lineal para la triangulación de polígonos monótonos", Pattern Recognition Letters , 2 (marzo): 155-158.
  14. ↑ Pickover, Clifford A., The Math Book , Sterling, 2009: pág. 184.

Enlaces