Pseudotriángulo

El pseudotriángulo entre tres conjuntos convexos suavizados (izquierda) y un pseudotriángulo poligonal (derecha)

En geometría euclídea bidimensional, un pseudotriángulo es un subconjunto simplemente conexo del plano que se encuentra entre tres convexidades tangentes entre sí. Una pseudotriangulación es una partición de una región del plano en pseudotriángulos, y una pseudotriangulación aguda es una pseudotriangulación en la que en cada vértice los bordes incidentes abarcan un ángulo de menos de π.

Aunque las palabras "pseudotriángulo" y "pseudotriangulación" se han usado con varios significados en matemáticas durante mucho tiempo, los términos^[1]​ que se usan en este artículo fueron introducidos en 1993 por Michel Pocchiola y Gert Vegter en relación con el cálculo de relaciones de visibilidad y bitangencia entre obstáculos convexos en el plano. Ileana Streinu (2000, 2005) consideró por primera vez las pseudotriangulaciones agudas como parte de su solución al problema de la regla de carpintero, una prueba de que cualquier cadena poligonal en el plano se puede enderezar mediante una secuencia de movimientos continuos. Las pseudotriangulaciones también se han utilizado para la detección de colisiones entre objetos en movimiento^[2]​ y para el dibujo dinámico de gráficos y la transformación de formas.^[3]​ Las pseudotriangulaciones agudas surgen en la teoría de la rigidez estructural como ejemplos de grafos planos,^[4]​ mínimamente rígidos y en métodos para colocar vigilantes en conexión con el problema de la galería de arte.^[5]​ El bombardeo antimatroide de un conjunto de puntos en el plano da lugar a pseudotriangulaciones agudas,^[6]​ aunque no todas las posibles pseudotriangulaciones agudas pueden generarse de esta manera.

Para una revisión detallada de gran parte del material discutido aquí, véase Rote, Santos y Streinu (2008).

Pseudotriángulos

Pocchiola y Vegter (1996a,b,c) originalmente definieron un pseudotriángulo como una región del plano simplemente conectada limitada por tres curvas convexas suaves que son tangentes en sus extremos. Sin embargo, el trabajo posterior se ha decidido por una definición más amplia que se aplica de manera más general a los polígono, así como a las regiones delimitadas por curvas suaves, y que permite ángulos distintos de cero en los tres vértices. En esta definición más amplia, un pseudotriángulo es una región del plano simplemente conectada, que tiene tres vértices convexos. Las tres curvas límite que conectan estos tres vértices deben ser convexas, en el sentido de que cualquier segmento de línea que conecte dos puntos en la misma curva límite debe estar completamente fuera o en el límite del pseudotriángulo. Así, el pseudotriángulo es la región entre los cascos convexos de estas tres curvas y, más generalmente, tres conjuntos convexos tangentes entre sí forman un pseudotriángulo que se encuentra entre ellos.

Para aplicaciones algorítmicas es de particular interés caracterizar pseudotriángulos que son polígonos. En un polígono, un vértice es "convexo" si abarca un ángulo interior menor que π, y "cóncavo" en caso contrario (en particular, consideramos que un ángulo de exactamente π es cóncavo). Cualquier polígono debe tener al menos tres ángulos convexos, porque el ángulo exterior total de un polígono es 2π, los ángulos convexos contribuyen menos que π cada uno a este total y los ángulos cóncavos contribuyen cero o cantidades negativas. Un pseudotriángulo poligonal es un polígono que tiene exactamente tres vértices convexos. En particular, cualquier triángulo y cualquier cuadrilátero no convexo es un pseudotriángulo.

El envolvente convexa de cualquier pseudotriángulo es un triángulo. Las curvas en el límite del pseudotriángulo entre cada par de vértices convexos se encuentran dentro del triángulo o coinciden con uno de sus bordes.

Pseudotriangulaciones

Una pseudotriangulación es una partición de una región del plano en pseudotriángulos. Cualquier triangulation de una región del plano es una pseudotriangulación. Si bien dos triangulaciones cualesquiera de la misma región deben tener el mismo número de aristas y triángulos, no ocurre lo mismo con las pseudotriangulaciones; por ejemplo, si la región es en sí misma un pseudotriángulo poligonal de vértices n, entonces una pseudotriangulación de la misma puede tener tan solo un pseudotriángulo y aristas n, o tantos como n − 2 pseudotriángulos y 2n − 3 aristas.

Una pseudotriangulación mínima es una pseudotriangulación T tal que ningún subgrafo de T es una pseudotriangulación que cubre la misma región convexa del plano. Una pseudotriangulación mínima con n vértices debe tener al menos 2n − 3 aristas; si tiene exactamente 2n − 3 aristas, debe ser una pseudotriangulación puntiaguda, pero existen pseudotriangulaciones mínimas con 3n − O(1) aristas.^[7]​

Agarwal et al. (2002) describen estructuras de datos para mantener pseudotriangulaciones de puntos móviles o polígonos móviles. Muestran que el uso de pseudotriangulaciones en lugar de triangulaciones permite que sus algoritmos mantengan estas estructuras con relativamente pocos cambios combinatorios a medida que se mueven las entradas, y usan estas pseudotriangulaciones dinámicas para realizar la detección de colisiones entre los objetos en movimiento.

Gudmundson et al. (2004) consideran el problema de encontrar una pseudotriangulación de un conjunto de puntos o polígono con una longitud de borde total mínima y proporcionan algoritmos de aproximación para este problema.

Pseudotriangulaciones agudas

Una secuencia de bombardeo de un conjunto de puntos en un plano (eliminando los puntos de los sucesivos polígonos envolventes convexos) y la pseudotriangulación aguda derivada de esta secuencia

Una pseudotriangulación aguda se puede definir como una colección finita de segmentos de línea que no se cruzan, de forma que en cada vértice los segmentos de línea incidentes abarquen un ángulo de como máximo π, y tal que no se puedan agregar segmentos de línea entre dos vértices existentes mientras se preserva esta propiedad. No es difícil ver que una pseudotriangulación aguda es una pseudotriangulación que abarca el recinto convexo que recubre el conjunto de los puntos dados: todos los bordes del recubrimiento convexo se pueden agregar conservando la propiedad de expansión de ángulos, y todas las caras interiores deben ser pseudotriángulos; de lo contrario, se podría agregar un segmento de línea bitangente entre dos vértices de una cara.

Una pseudotriangulación aguda con vértices en v debe tener exactamente 2v − 3 aristas.^[8]​ Esto sigue a un argumento doble conteo simple que involucra la característica de Euler: como cada cara excepto la exterior es un pseudotriángulo, con tres ángulos convexos, la pseudotriangulación debe tener 3f − 3 ángulos convexos entre bordes adyacentes. Cada arista es el borde en el sentido de las agujas del reloj para dos ángulos, por lo que hay un total de 2 ángulos "e", de los cuales todos menos "v" son convexos. Así, 3f − 3 = 2e − v. Combinando esto con la ecuación de Euler f − e + v = 2 y resolviendo el sistema de ecuaciones lineales resultante se obtiene que e = 2v − 3. El mismo argumento también demuestra que f = v − 1 (incluyendo el casco convexo como una de las caras), por lo que la pseudotriangulación debe tener exactamente v − 2 pseudotriángulos.

De manera similar, dado que cualquier subgrafo con k vértices de una pseudotriangulación aguda puede completarse para formar una pseudotriangulación aguda de sus vértices, el subgrafo debe tener como máximo 2k − 3 aristas. Por lo tanto, las pseudotriangulaciones agudas satisfacen las condiciones que definen un grafo de Laman: tienen exactamente 2v − 3 aristas, y sus subgrafos de k vértices tienen como máximo 2k − 3 aristas. Los grafos de Laman, y por lo tanto también las pseudotriangulaciones agudas, son gráficos mínimamente rígidos en dos dimensiones. Cada grafo plano de Laman se puede dibujar como una pseudotriangulación aguda, aunque no todos los dibujos planos de un grafo plano de Laman son una pseudotriangulación.^[9]​

Otra forma de encontrar una pseudotriangulación aguda es "descascarar" un conjunto de puntos; es decir, eliminar los vértices de la envolvente convexa uno por uno hasta que se hayan eliminado todos los puntos. La familia de secuencias de eliminaciones que se puede formar de esta manera es el antimatroide de bombardeo del conjunto de puntos, y el conjunto de perímetros convexos de la secuencia de conjuntos de puntos formada por este proceso de eliminación forma una pseudotriangulación.^[6]​ Sin embargo, no todas las pseudotriangulaciones agudas se pueden formar de esta manera.

Aichholzer et al. (2004) muestran que un conjunto de n puntos, de los cuales h pertenecen a la envolvente convexa del conjunto, debe tener al menos C_h−2×3^n−h pseudotriangulaciones agudas diferentes, donde C_i denota el i-ésimo número de Catalan. Como consecuencia, muestran que los conjuntos de puntos con la menor cantidad de pseudotriangulaciones agudas son los conjuntos de vértices de polígonos convexos. Aichholzer et al. (2006) investigan conjuntos de puntos con un gran número de pseudotriangulaciones agudas. Los investigadores de geometría computacional también han proporcionado algoritmos para enumerar todas las pseudotriangulaciones agudas de un conjunto de puntos en una pequeña cantidad de tiempo por pseudotriangulación.^[10]​

Véase también

• Curva deltoide
• Triángulo circular

Referencias

1. Para "pseudo-triángulo" véase por ejemplo, Whitehead, J. H. C. (1961), «Manifolds with transverse fields in Euclidean space», Annals of Mathematics 73 (1): 154-212, JSTOR 1970286, MR 0124917, doi:10.2307/1970286 .. En su página 196, este documento se refiere a una "condición de pseudotriángulo" en la aproximación funcional. Para "pseudotriangulación" véase, por ejemplo, Belaga, È. G. (1976), «[Heawood vectors of pseudotriangulations]», Doklady Akademii Nauk SSSR (en russian) 231 (1): 14-17, MR 0447029 ..
2. Agarwal et al. (2002).
3. Streinu (2006).
4. Haas et al. (2005)
5. Speckmann and Tóth (2005).
6. Har-Peled (2002).
7. Rote, Wang, Wang, and Xu (2003), Theorem 4 and Figure 4.
8. Primero demostrado por Streinu (2000), pero el argumento que se da aquí es de Haas et al. (2005), Lemma 5.
9. Haas et al. (2005).
10. Bereg (2005); Brönnimann et al. (2006).

Bibliografía

• Agarwal, Pankaj K.; Basch, Julien; Guibas, Leonidas J.; Hershberger, John; Zhang, Li (2002), «Deformable free-space tilings for kinetic collision detection», International Journal of Robotics Research 21 (3): 179-197, S2CID 11907465, doi:10.1177/027836402320556395 ..
• Aichholzer, Oswin; Aurenhammer, Franz; Krasser, Hannes; Speckmann, Bettina (2004), «Convexity minimizes pseudo-triangulations», Computational Geometry Theory and Applications 28 (1): 3-10, MR 2070708, doi:10.1016/j.comgeo.2004.01.002 .. Versión preliminar en Canadá. Conf. computar Geom., 2002.
• Aichholzer, Oswin; Orden, David; Santos, Francisco; Speckmann, Bettina (2008), «On the number of pseudo-triangulations of certain point sets», Journal of Combinatorial Theory, Series A 115 (2): 254-278, MR 2382515, S2CID 1189243, arXiv:math/0601747, doi:10.1016/j.jcta.2007.06.002 .
• Bereg, Sergey (2005), «Enumerating pseudo-triangulations in the plane», Computational Geometry Theory and Applications 30 (3): 207-222, MR 2123970, doi:10.1016/j.comgeo.2004.09.002 ..
• Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack (2006), «Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm», SIAM Journal on Computing 36 (3): 721-739, MR 2263009, doi:10.1137/050631008 ..
• Gudmundsson, Joachim; Levcopoulos, Christos; Kamal, Lodaya; Meena, Mahajan (2004), «Minimum weight pseudo-triangulations», en Lodaya, Kamal; Mahajan, Meena, eds., FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science 3328, Springer-Verlag, pp. 299-310, ISBN 978-3-540-24058-7, arXiv:0705.3888, doi:10.1007/b104325, archivado desde el original el 6 de febrero de 2012, consultado el 4 de julio de 2022 ..
• Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana et al. (2005), «Planar minimally rigid graphs and pseudo-triangulations», Computational Geometry Theory and Applications 31 (1–2): 31-61, MR 2131802, S2CID 38637747, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003  Se sugiere usar |número-autores= (ayuda)..
• Har-Peled, Sariel (2002), A comment on pseudo-triangulation in three dimensions, archivado desde el original el 12 de septiembre de 2006, consultado el 12 de abril de 2007 ..
• Pocchiola, Michel; Vegter, Gert (1996a), «The visibility complex», International Journal of Computational Geometry and Applications 6 (3): 297-308, doi:10.1142/S0218195996000204, archivado desde el original el 3 de diciembre de 2006 .. Versión preliminar en Ninth ACM Symp. Geometría Computacional (1993) 328–337.
• Pocchiola, Michel; Vegter, Gert (1996b), «Topologically sweeping visibility complexes via pseudotriangulations», Discrete and Computational Geometry 16 (4): 419-453, MR 1414964, doi:10.1007/BF02712876 ..
• Pocchiola, Michel; Vegter, Gert (1996c), «Pseudo-triangulations: theory and applications», Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 291-300, S2CID 15948239, doi:10.1145/237218.237398, archivado desde el original el 6 de febrero de 2007, consultado el 4 de julio de 2022 ..
• Rote, Günter; Santos, Francisco; Streinu, Ileana (2003), «Expansive motions and the polytope of pointed pseudo-triangulations», Discrete and Computational Geometry — The Goodman–Pollack Festschrift, Springer-Verlag, pp. 699-736, S2CID 14689476, arXiv:math.CO/0206027, doi:10.1007/978-3-642-55566-4_33 ..
• Rote, Günter; Santos, Francisco; Streinu, Ileana (2008), «Pseudo-triangulations — a survey», Surveys on discrete and computational geometry, Contemporary Mathematics 453, Providence, RI: American Mathematical Society, pp. 343-410, MR 2405689 ..
• Rote, Günter; Wang, Cao An; Wang, Lusheng; Xu, Yinfeng (2003), «On constrained minimum pseudotriangulations», Computing and Combinatorics, Lecture Notes in Computer Science 2697, Springer-Verlag, pp. 445-454, archivado desde el original el 5 de febrero de 2012, consultado el 4 de julio de 2022 ..
• Speckmann, Bettina; Tóth, Csaba D. (2005), «Allocating vertex π-Guards in simple polygons via pseudo-triangulations», Discrete and Computational Geometry 33 (2): 345-364, MR 2121300, doi:10.1007/s00454-004-1091-9 ..
• Streinu, Ileana (2000), «A combinatorial approach to planar non-colliding robot arm motion planning», Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 443-453, S2CID 9420124, doi:10.1109/SFCS.2000.892132 . (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)..
• Streinu, Ileana (2005), «Pseudo-triangulations, rigidity and motion planning», Discrete and Computational Geometry 34 (4): 587-635, MR 2173930, doi:10.1007/s00454-005-1184-0 ..
• Streinu, Ileana (2006), «Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs», Proc. Int. Symp. Graph Drawing (GD 2005), Springer-Verlag, Lecture Notes in Computer Science 3843, pp. 421-433 ..