Triangulación de puntos

Complejo simplicial en geometría euclidiana

Dos triangulaciones diferentes del mismo conjunto de 9 puntos en el plano.

Una triangulación de un conjunto de puntos en el espacio euclidiano es un complejo simplicial que cubre la envoltura convexa de , y cuyos vértices pertenecen a . ^[1] En el plano (cuando es un conjunto de puntos en ), las triangulaciones están formadas por triángulos, junto con sus aristas y vértices. Algunos autores requieren que todos los puntos de sean vértices de sus triangulaciones. ^[2] En este caso, una triangulación de un conjunto de puntos en el plano puede definirse alternativamente como un conjunto máximo de aristas que no se cruzan entre puntos de . En el plano, las triangulaciones son casos especiales de grafos de líneas rectas planas . ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$

Un tipo de triangulación particularmente interesante son las triangulaciones de Delaunay . Son los duales geométricos de los diagramas de Voronoi . La triangulación de Delaunay de un conjunto de puntos en el plano contiene el gráfico de Gabriel , el gráfico del vecino más próximo y el árbol de expansión mínimo de . ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$

Las triangulaciones tienen varias aplicaciones y es interesante encontrar las "buenas" triangulaciones de un conjunto de puntos dado bajo ciertos criterios, como por ejemplo las triangulaciones de peso mínimo . A veces es deseable tener una triangulación con propiedades especiales, por ejemplo, en la que todos los triángulos tengan ángulos grandes (se evitan los triángulos largos y estrechos ("astillados")). ^[3]

Dado un conjunto de aristas que conectan puntos del plano, el problema de determinar si contienen una triangulación es NP-completo . ^[4]

Triangulaciones regulares

Algunas triangulaciones de un conjunto de puntos se pueden obtener elevando los puntos de a (lo que equivale a añadir una coordenada a cada punto de ), calculando la envoltura convexa del conjunto de puntos elevados y proyectando las caras inferiores de esta envoltura convexa de nuevo sobre . Las triangulaciones construidas de esta manera se denominan triangulaciones regulares de . Cuando los puntos se elevan al paraboloide de ecuación , esta construcción da como resultado la triangulación de Delaunay de . Tenga en cuenta que, para que esta construcción proporcione una triangulación, la envoltura convexa inferior del conjunto de puntos elevados debe ser simplicial . En el caso de las triangulaciones de Delaunay, esto equivale a exigir que ningún punto de se encuentre en la misma esfera. ${\displaystyle {\mathcal {P}}\subset \mathbb {R} ^{d}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \mathbb {R} ^{d+1}}$ ${\displaystyle x_{d+1}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle d+2}$ ${\displaystyle {\mathcal {P}}}$

Combinatoria en el plano

Toda triangulación de cualquier conjunto de puntos en el plano tiene triángulos y aristas donde es el número de puntos de en el límite de la envoltura convexa de . Esto se desprende de un argumento característico de Euler sencillo. ^[5] ${\displaystyle {\mathcal {P}}}$ ${\displaystyle n}$ ${\displaystyle 2n-h-2}$ ${\displaystyle 3n-h-3}$ ${\displaystyle h}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$

Algoritmos para construir triangulaciones en el plano

Algoritmo de división de triángulos  : encuentre la envoltura convexa del conjunto de puntos y triangule esta envoltura como un polígono. Elija un punto interior y dibuje aristas hasta los tres vértices del triángulo que lo contiene. Continúe este proceso hasta que se hayan agotado todos los puntos interiores. ^[6] ${\displaystyle {\mathcal {P}}}$

Algoritmo incremental  : ordenar los puntos de según las coordenadas x. Los primeros tres puntos determinan un triángulo. Considerar el siguiente punto en el conjunto ordenado y conectarlo con todos los puntos considerados previamente que sean visibles para p. Continuar este proceso de agregar un punto de a la vez hasta que se hayan procesado todos los de. ^[7] ${\displaystyle {\mathcal {P}}}$ ${\displaystyle p}$ ${\displaystyle \{p_{1},...,p_{k}\}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$

Complejidad temporal de varios algoritmos

La siguiente tabla reporta resultados de complejidad temporal para la construcción de triangulaciones de conjuntos de puntos en el plano, bajo diferentes criterios de optimalidad, donde es el número de puntos. ${\displaystyle n}$

Véase también

• Generación de malla
• Triangulación de polígonos

Notas

1. De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010). Triangulaciones, estructuras para algoritmos y aplicaciones . Algoritmos y computación en matemáticas. Vol. 25. Springer.
2. de Berg y otros. 2008, Sección 9.1.
3. de Berg, Marcos ; Otfried Cheong ; Marc van Kreveld; Mark Overmars (2008). Geometría computacional: algoritmos y aplicaciones (PDF) . Springer-Verlag. ISBN 978-3-540-77973-5.
4. Lloyd 1977.
5. Edelsbrunner, Herbert ; Tan, Tiow Seng; Waupotitsch, Roman (1992), "Un algoritmo de tiempo O ( n ²  log  n ) para la triangulación de ángulos minmax", SIAM Journal on Scientific and Statistical Computing , 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895 , doi :10.1137/0913058, MR  1166172 .
6. Devadoss, O'Rourke Geometría discreta y computacional . Princeton University Press, 2011, pág. 60.
7. Devadoss, O'Rourke Geometría discreta y computacional . Princeton University Press, 2011, pág. 62.
8. Edelsbrunner, Tan y Waupotitsch 1990.
9. Berna y otros 1993.
10. Chazelle, Guibas y Lee 1985.
11. Vassilev 2005.
12. Jansen 1992.
13. Fekete 2012.
14. Edelsbrunner y Tan 1991.

Referencias

• Bern, M.; Edelsbrunner, H .; Eppstein, D .; Mitchell, S.; Tan, TS (1993), "Inserción de aristas para triangulaciones óptimas", Geometría discreta y computacional , 10 (1): 47–65, doi : 10.1007/BF02573962 , MR  1215322
• Chazelle, Bernard; Guibas, Leo J.; Lee, DT (1985). "El poder de la dualidad geométrica" ​​(PDF) . BIT . 25 (1). BIT Ciencias de la Computación y Matemáticas Numéricas: 76–90. doi :10.1007/BF01934990. ISSN  0006-3835. S2CID  122411548.
• de Berg, Mark; van Kreveld, Marc; Overmars, Marcos; Schwarzkopf, Otfried (2008). Geometría computacional: algoritmos y aplicaciones (3 ed.). Springer-Verlag.
• O'Rourke, Joseph; L. Devadoss, Satyan (2011). Geometría discreta y computacional (1.ª ed.). Princeton University Press.
• Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1990). Un algoritmo de tiempo O(n2log n) para la triangulación de ángulos MinMax . Actas del sexto simposio anual sobre geometría computacional. SCG '90. ACM. págs. 44–52. CiteSeerX  10.1.1.66.2895 . doi :10.1145/98524.98535. ISBN . 0-89791-362-0.
• Edelsbrunner, Herbert; Tan, Tiow Seng (1991). Un algoritmo de tiempo cuadrático para la triangulación de longitud minmax . 32.º Simposio anual sobre fundamentos de la informática. pp. 414–423. CiteSeerX  10.1.1.66.8959 . doi :10.1109/SFCS.1991.185400. ISBN . 0-8186-2445-0.
• Fekete, Sándor P. (2012). "La complejidad de la triangulación de longitud MaxMin". arXiv : 1208.0202v1 [cs.CG].
• Jansen, Klaus (1992). La complejidad del problema de triangulación de grados mín-máx (PDF) . 9.º Taller europeo sobre geometría computacional. págs. 40–43.
• Lloyd, Errol Lynn (1977). Sobre triangulaciones de un conjunto de puntos en el plano . 18.º Simposio anual sobre fundamentos de la informática. Teoría de conmutación y autómatas, 1974., IEEE Conference Record of 15th Annual Symposium on . pp. 228–240. doi :10.1109/SFCS.1977.21. ISSN  0272-5428.
• Vassilev, Tzvetalin Simeonov (2005). Triangulación de área óptima (PDF) (Ph.D.). Universidad de Saskatchewan, Saskatoon. Archivado desde el original (PDF) el 13 de agosto de 2017 . Consultado el 15 de junio de 2013 .