Triangulación de puntos

Complejo simplicial en geometría euclidiana

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

Una triangulación de un conjunto de puntos en el espacio euclidiano es un complejo simple que cubre la cáscara 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 exigen 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 se puede definir alternativamente como un conjunto máximo de aristas que no se cruzan entre puntos de . En el plano, las triangulaciones son casos especiales de gráficas planas rectilíneas . ${\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 triangulaciones 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 vecino más cercano y el árbol de expansión mínimo de . ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$

Las triangulaciones tienen varias aplicaciones y existe interés en encontrar las "buenas" triangulaciones de un punto determinado establecido bajo algunos criterios como, por ejemplo, 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

Se pueden obtener algunas triangulaciones de un conjunto de puntos elevando los puntos de hacia (lo que equivale a agregar una coordenada a cada punto de ), calculando el casco convexo del conjunto de puntos elevado y proyectando las caras inferiores de este conjunto de puntos convexo. casco de nuevo . Las triangulaciones construidas de esta manera se denominan triangulaciones regulares de . Cuando los puntos se elevan al paraboloide de la ecuación , esta construcción da como resultado la triangulación de Delaunay . Tenga en cuenta que, para que esta construcción proporcione una triangulación, el casco convexo inferior del conjunto de puntos elevados debe ser simple . En el caso de las triangulaciones de Delaunay, esto equivale a exigir que ningún punto 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.

Cada 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 del casco convexo de . Esto se desprende de un sencillo argumento característico de Euler . ^[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 el casco convexo del conjunto de puntos y triangule este casco como un polígono. Elige un punto interior y dibuja aristas a los tres vértices del triángulo que lo contiene. Continúe este proceso hasta que se agoten todos los puntos interiores. ^[6] ${\displaystyle {\mathcal {P}}}$

Algoritmo incremental  : ordena los puntos según las coordenadas x. Los primeros tres puntos determinan un triángulo. Considere el siguiente punto del conjunto ordenado y conéctelo con todos los puntos considerados anteriormente que son visibles en la p. Continúe este proceso de agregar un punto a la vez hasta que se haya procesado todo . ^[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 optimización, donde es el número de puntos. ${\displaystyle n}$

Ver 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. Saltador.
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", Revista SIAM de Computación científica y estadística , 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895 , doi :10.1137/0913058, SEÑOR  1166172 .
6. Devadoss, O'Rourke Geometría computacional y discreta . Prensa de la Universidad de Princeton, 2011, pág. 60.
7. Devadoss, O'Rourke Geometría computacional y discreta . Prensa de la Universidad de Princeton, 2011, pág. 62.
8. Edelsbrunner, Tan y Waupotitsch 1990.
9. Berna et al. 1993.
10. Chazelle, Guibas y Lee 1985.
11. Vassilev 2005.
12. Jansen 1992.
13. Fekete 2012.
14. Edelsbrunner y Tan 1991.

Referencias

• Berna, M.; Edelsbrunner, H .; Eppstein, D .; Mitchell, S.; Tan, TS (1993), "Inserción de bordes para triangulaciones óptimas", Geometría computacional y discreta , 10 (1): 47–65, doi : 10.1007/BF02573962 , SEÑOR  1215322
• Chazelle, Bernard; Guibas, Leo J.; Lee, DT (1985). "El poder de la dualidad geométrica" ​​(PDF) . POCO . 25 (1). BIT Informática 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, José; L. Devadoss, Satyan (2011). Geometría discreta y computacional (1 ed.). Prensa de la Universidad de Princeton.
• Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, romano (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; Bronceado, 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. págs. 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ínimo-máximo (PDF) . IX 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., Registro de la conferencia IEEE del 15º Simposio anual en . págs. 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 .