Una triangulación de un conjunto de puntos. en el espacio euclidiano es un complejo simplicial que cubre el casco convexo de, y cuyos vértices pertenecen a . [1] En el avión (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 deson 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 bordes que no se cruzan entre puntos de . En el plano, las triangulaciones son casos especiales de gráficos de línea recta plana .
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 puntosen el plano contiene el gráfico de Gabriel , el gráfico vecino más cercano y el árbol de expansión mínimo de.
Las triangulaciones tienen una serie de aplicaciones, y hay interés en encontrar las triangulaciones "buenas" de un conjunto de puntos dado 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 tienen ángulos grandes (se evitan los triángulos largos y estrechos ("astillados")). [3]
Dado un conjunto de aristas que conectan puntos del plano, el problema para determinar si contienen una triangulación es NP-completo . [4]
Triangulaciones regulares
Algunas triangulaciones de un conjunto de puntos se puede obtener levantando los puntos de dentro (que equivale a agregar una coordenada a cada punto de ), calculando el casco convexo del conjunto de puntos elevados y proyectando las caras inferiores de este casco convexo hacia atrás en . Las triangulaciones construidas de esta manera se conocen como 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 de. 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 requerir que no puntos de yacen en la misma esfera.
Combinatoria en el avión
Cada triangulación de cualquier conjunto de puntos en el plano tiene triángulos y bordes 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]
Algoritmos para construir triangulaciones en el plano.
Algoritmo de división de triángulos : encuentre el casco convexo del conjunto de puntosy triangular este casco como un polígono. Elija un punto interior y dibuje los bordes de los tres vértices del triángulo que lo contiene. Continúe este proceso hasta que se agoten todos los puntos interiores. [6]
Algoritmo incremental : ordena los puntos desegún las coordenadas x. Los primeros tres puntos determinan un triángulo. Considere el siguiente punto en el conjunto ordenado y conectarlo con todos los puntos considerados previamente que son visibles para p. Continúe este proceso de agregar un punto de a la vez hasta que todos ha sido procesado. [7]
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.
minimizar | maximizar | ||
---|---|---|---|
mínimo | ángulo | ( Triangulación de Delaunay ) | |
máximo | [8] [9] | ||
mínimo | área | [10] | [11] |
máximo | [11] | ||
máximo | la licenciatura | NP-completo para el grado 7 [12] | |
máximo | excentricidad | [9] | |
mínimo | longitud de borde | ( Problema del par de puntos más cercano ) | NP-completo [13] |
máximo | [14] | (usando el casco convexo ) | |
la suma de | NP-hard ( triangulación de peso mínimo ) | ||
mínimo | altura | [9] | |
máximo | Pendiente | [9] |
Ver también
Notas
- ^ De Loera, Jesús A .; Rambau, Jörg; Santos, Francisco (2010). Triangulaciones, estructuras para algoritmos y aplicaciones . Algoritmos y Computación en Matemáticas. 25 . Saltador.
- ^ de Berg y col. 2008 , Sección 9.1.
- ^ de Berg, Mark ; Otfried Cheong ; Marc van Kreveld; Mark Overmars (2008). Geometría computacional: algoritmos y aplicaciones (PDF) . Springer-Verlag. ISBN 978-3-540-77973-5.
- ^ Lloyd 1977 .
- ^ Edelsbrunner, Herbert ; Tan, Tiow Seng; Waupotitsch, Roman (1992), "Un algoritmo de tiempo O ( n 2 log n ) para la triangulación del ángulo mínimo máx.", SIAM Journal on Scientific and Statistical Computing , 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895 , doi : 10.1137 / 0913058 , MR 1166172.
- ^ Geometría computacional y discreta de Devadoss, O'Rourke. Prensa de la Universidad de Princeton, 2011, pág. 60.
- ^ Geometría computacional y discreta de Devadoss, O'Rourke. Prensa de la Universidad de Princeton, 2011, pág. 62.
- ^ Edelsbrunner, Tan y Waupotitsch 1990 .
- ^ a b c d Berna y col. 1993 .
- ^ Chazelle, Guibas y Lee 1985 .
- ↑ a b Vassilev, 2005 .
- ^ Jansen 1992 .
- ^ Fekete 2012 .
- ^ 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 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 . BIT Ciencias de la Computación y Matemática Numérica. 25 (1): 76–90. doi : 10.1007 / BF01934990 . ISSN 0006-3835 . S2CID 122411548 .
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark; 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.). Prensa de la Universidad de Princeton.
- Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1990). Un algoritmo de tiempo O (n2log n) para la triangulación del ángulo 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. 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 Workshop Europeo de 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. Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on . 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 .