En la geometría del plano euclidiano , un pseudotriángulo ( pseudo-triángulo ) es el subconjunto simplemente conectado del plano que se encuentra entre tres conjuntos convexos mutuamente tangentes . Una pseudotriangulación ( pseudo-triangulaciones ) es una partición de una región del plano en pseudotriangulaciones, y una pseudotriangulación puntiaguda es una pseudotriangulación en la que en cada vértice los bordes incidentes abarcan un ángulo menor que π.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/a1/Pseudotriangles.svg/310px-Pseudotriangles.svg.png)
Aunque las palabras "pseudotriangulo" y "pseudotriangulación" se han utilizado con varios significados en matemáticas durante mucho más tiempo, [1] los términos como se usan aquí fueron introducidos en 1993 por Michel Pocchiola y Gert Vegter en conexión con el cálculo de relaciones de visibilidad y bitangentes entre obstáculos convexos en el avión. Las pseudotriangulaciones puntiagudas fueron consideradas por primera vez por Ileana Streinu (2000, 2005) como parte de su solución al problema de la regla de carpintero , una prueba de que cualquier camino poligonal simple en el plano puede enderezarse 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 puntiagudas surgen en la teoría de la rigidez como ejemplos de gráficos planares mínimamente rígidos , [4] y en los métodos para colocar guardas en relación con el teorema de la galería de arte . [5] El antimatroide de bombardeo de un conjunto de puntos planos da lugar a pseudotriangulaciones puntiagudas, [6] aunque no todas las pseudotriangulaciones puntiagudas pueden surgir de esta manera.
Para una revisión detallada de gran parte del material discutido aquí, ver Rote, Santos y Streinu (2008).
Pseudotriangulos
Pocchiola y Vegter (1996a, b, c) originalmente definieron un pseudotriángulo como una región simplemente conectada del plano delimitada por tres curvas convexas suaves que son tangentes en sus puntos finales. Sin embargo, el trabajo posterior se ha basado en una definición más amplia que se aplica de manera más general a los polígonos , 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 de 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 de límite debe estar completamente fuera o en el límite del pseudotriángulo. Por lo tanto, el pseudotriángulo es la región entre los cascos convexos de estas tres curvas y, de manera más general, tres conjuntos convexos mutuamente tangentes 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 de π cada uno a este total, y los ángulos cóncavos contribuyen con cantidades cero o 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 casco convexo de cualquier pseudotriángulo es un triángulo. Las curvas a lo largo del 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 pseudotriangulos. Cualquier triangulación 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 n- vértices, entonces una pseudotriangulación de la misma puede tener tan solo un pseudotriangulo yn bordes, o tanto como n - 2 pseudotriángulos y 2 n - 3 bordes.
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 2 n - 3 aristas; si tiene exactamente 2 n - 3 aristas, debe ser una pseudotriangulación puntiaguda, pero existen pseudotriangulaciones mínimas con 3 n - O (1) aristas. [7]
Agarwal y col. (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 utilizan estas pseudotriangulaciones dinámicas para realizar la detección de colisiones entre los objetos en movimiento.
Gudmundsson y col. (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.
Seudotriangulaciones puntiagudas
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/37/Convex_shelling.svg/310px-Convex_shelling.svg.png)
Una pseudotriangulación puntiaguda se puede definir como una colección finita que no se cruza de segmentos de línea, de modo que en cada vértice los segmentos de línea incidente abarcan un ángulo de π como máximo, y de tal manera que no se pueden agregar segmentos de línea entre dos vértices existentes mientras se conserva esta propiedad. No es difícil ver que una pseudotriangulación puntiaguda es una pseudotriangulación de su casco convexo: se pueden agregar todos los bordes convexos del casco mientras se preserva la propiedad de extensión del ángulo, y todas las caras interiores deben ser pseudotriangulos, de lo contrario se podría agregar un segmento de línea bitangente entre dos vértices de la cara.
Una pseudotriangulación puntiaguda con v vértices debe tener exactamente 2 v - 3 aristas. [8] Esto sigue por un argumento de conteo doble simple que involucra la característica de Euler : como cada cara, excepto la externa, es un pseudotriángulo, con tres ángulos convexos, la pseudotriangulación debe tener 3 f - 3 ángulos convexos entre bordes adyacentes. Cada borde 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. Por lo tanto, 3 f - 3 = 2 e - v . Combinando esto con la ecuación de Euler f - e + v = 2 y resolviendo las ecuaciones lineales simultáneas resultantes , se obtiene e = 2 v - 3. El mismo argumento también muestra que f = v - 1 (incluyendo el casco convexo como una de las caras) , por lo que la pseudotriangulación debe tener exactamente v - 2 pseudotriangulos.
De manera similar, dado que cualquier subgrafo k -vertex de una pseudotriangulación puntiaguda se puede completar para formar una pseudotriangulación puntiaguda de sus vértices, el subgrafo debe tener como máximo 2 k - 3 aristas. Por lo tanto, las pseudotriangulaciones puntiagudas satisfacen las condiciones que definen las gráficas de Laman : tienen exactamente 2 v - 3 aristas, y sus subgrafias k -vertex tienen como máximo 2 k - 3 aristas. Los gráficos de Laman, y por lo tanto también las pseudotriangulaciones puntiagudas, son gráficos mínimamente rígidos en dos dimensiones. Cada gráfico plano de Laman se puede dibujar como una pseudotriangulación puntiaguda, aunque no todos los dibujos planos de un gráfico plano de Laman es una pseudotriangulación. [9]
Otra forma de encontrar una pseudotriangulación puntiaguda es descascarar un conjunto de puntos; es decir, para eliminar los vértices convexos del casco uno por uno hasta que se hayan eliminado todos los puntos. La familia de secuencias de extracciones que se pueden formar de esta manera es el antimatroide de bombardeo del conjunto de puntos, y el conjunto de bordes de cascos convexos de la secuencia de conjuntos de puntos formados por este proceso de remoción forma una pseudotriangulación. [6] Sin embargo, no todas las pseudotriangulaciones puntiagudas pueden formarse de esta manera.
Aichholzer y col. (2004) muestran que un conjunto de n puntos, h de los cuales pertenecen al casco convexo del conjunto, debe tener al menos C h −2 × 3 n - h pseudotriangulaciones puntiagudas diferentes, donde C i denota el i ésimo número catalán . Como consecuencia, muestran que los conjuntos de puntos con la menor cantidad de pseudotriangulaciones puntiagudas son los conjuntos de vértices de polígonos convexos. Aichholzer y col. (2006) investigan conjuntos de puntos con un gran número de pseudotriangulaciones puntiagudas. Los investigadores de geometría computacional también han proporcionado algoritmos para enumerar todas las pseudotriangulaciones puntiagudas de un conjunto de puntos en una pequeña cantidad de tiempo por pseudotriangulación. [10]
Ver también
Notas
- ↑ Para "pseudo-triángulo", ver, por ejemplo, Whitehead, JHC (1961), "Manifolds with transverse fields in Euclidean space", Annals of Mathematics , 73 (1): 154-212, doi : 10.2307 / 1970286 , JSTOR 1970286 , Señor 0124917. En la página 196, este artículo se refiere a una "condición de pseudo-triángulo" en aproximación funcional. Para "pseudo-triangulación", consulte, por ejemplo, Belaga, È. G. (1976), "[Vectores Heawood de pseudotriangulaciones]", Doklady Akademii Nauk SSSR (en ruso), 231 (1): 14-17, MR 0447029.
- ^ Agarwal y col. (2002).
- ^ Streinu (2006).
- ^ Haas y col. (2005)
- ^ Speckmann y Tóth (2005).
- ↑ a b Har-Peled (2002).
- ^ Rote, Wang, Wang y Xu (2003), Teorema 4 y Figura 4.
- ^ Primero mostrado por Streinu (2000), pero el argumento que damos aquí es de Haas et al. (2005), Lema 5.
- ^ Haas y col. (2005).
- ^ Bereg (2005); Brönnimann y col. (2006).
Referencias
- Agarwal, Pankaj K .; Basch, Julien; Guibas, Leonidas J .; Hershberger, John ; Zhang, Li (2002), "Mosaicos de espacio libre deformables para la detección de colisiones cinéticas", International Journal of Robotics Research , 21 (3): 179-197, doi : 10.1177 / 027836402320556395.
- Aichholzer, Oswin; Aurenhammer, Franz ; Krasser, Hannes; Speckmann, Bettina (2004), "La convexidad minimiza las pseudo-triangulaciones", Teoría y aplicaciones de la geometría computacional , 28 (1): 3–10, doi : 10.1016 / j.comgeo.2004.01.002 , MR 2070708. Versión preliminar en Canadá. Conf. Computación. Geom., 2002 .
- Aichholzer, Oswin; Orden, David; Santos, Francisco ; Speckmann, Bettina (2008), "Sobre el número de pseudo-triangulaciones de ciertos conjuntos de puntos", Journal of Combinatorial Theory, Serie A , 115 (2): 254-278, arXiv : math / 0601747 , doi : 10.1016 / j. jcta.2007.06.002 , MR 2382515
- Bereg, Sergey (2005), "Enumeración de pseudo-triangulaciones en el plano", Teoría y aplicaciones de la geometría computacional , 30 (3): 207–222, doi : 10.1016 / j.comgeo.2004.09.002 , MR 2123970.
- Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack (2006), "Contar y enumerar pseudotriangulaciones puntiagudas con el algoritmo de volteo codicioso", SIAM Journal on Computing , 36 (3): 721–739, doi : 10.1137 / 050631008 , MR 2263009.
- Gudmundsson, Joachim; Levcopoulos, Christos; Kamal, Lodaya; Meena, Mahajan (2004), " Pseudo -triangulaciones de peso mínimo" (PDF) , en Lodaya, Kamal; Mahajan, Meena (eds.), FSTTCS 2004: Fundamentos de la tecnología del software y la informática teórica , Lecture Notes in Computer Science, 3328 , Springer-Verlag, págs. 299-310, arXiv : 0705.3888 , doi : 10.1007 / b104325 , ISBN 978-3-540-24058-7.
- Haas, Ruth ; Orden, David; Rote, Günter; Santos, Francisco ; Servacio, Brigitte ; Servacio, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005), "Gráficos planos mínimamente rígidos y pseudo-triangulaciones", Teoría y aplicaciones de la geometría computacional , 31 (1-2): 31-61, arXiv : math / 0307347 , doi : 10.1016 / j.comgeo.2004.07 0.003 , MR 2131802.
- Har-Peled, Sariel (2002), Un comentario sobre la pseudo-triangulación en tres dimensiones , Archivado desde el original en 2006-09-12 , recuperada 2007-04-12.
- Pocchiola, Michel; Vegter, Gert (1996a), "El complejo de visibilidad" , International Journal of Computational Geometry and Applications , 6 (3): 297–308, doi : 10.1142 / S0218195996000204 , archivado desde el original el 2006-12-03. Versión preliminar en Noveno ACM Symp. Geometría computacional (1993) 328–337 .
- Pocchiola, Michel; Vegter, Gert (1996b), "Complejos de visibilidad de barrido topológico mediante pseudotriangulaciones", Geometría discreta y computacional , 16 (4): 419–453, doi : 10.1007 / BF02712876 , MR 1414964.
- Pocchiola, Michel; Vegter, Gert (1996c), "Pseudo-triangulaciones: teoría y aplicaciones" , Actas del 12º Simposio Anual de ACM sobre Geometría Computacional , págs. 291–300, doi : 10.1145 / 237218.237398.
- Rote, Günter; Santos, Francisco ; Streinu, Ileana (2003), " Movimientos expansivos y el politopo de pseudo-triangulaciones puntiagudas", Geometría discreta y computacional - The Goodman – Pollack Festschrift , Springer-Verlag, págs. 699–736, arXiv : math.CO/0206027 , doi : 10.1007 / 978-3-642-55566-4_33.
- Rote, Günter; Santos, Francisco ; Streinu, Ileana (2008), "Pseudo-triangulaciones - una encuesta", Encuestas sobre geometría discreta y computacional , Matemáticas contemporáneas, 453 , Providence, RI: American Mathematical Society, págs. 343–410, MR 2405689.
- Rote, Günter; Wang, Cao An; Wang, Lusheng; Xu, Yinfeng (2003), "Sobre pseudotriangulaciones mínimas restringidas" (PDF) , Computación y combinatoria , Lecture Notes in Computer Science, 2697 , Springer-Verlag, págs. 445–454.
- Speckmann, Bettina ; Tóth, Csaba D. (2005), "Asignación de protectores π de vértice en polígonos simples mediante pseudo-triangulaciones", Geometría discreta y computacional , 33 (2): 345–364, doi : 10.1007 / s00454-004-1091-9 , Señor 2121300.
- Streinu, Ileana (2000), "Un enfoque combinatorio para la planificación del movimiento del brazo robótico plano sin colisión" , Actas del 41º Simposio anual sobre los fundamentos de la informática , IEEE Computer Society, págs. 443–453, doi : 10.1109 / SFCS. 2000.892132.
- Streinu, Ileana (2005), "Pseudo-triangulaciones, rigidez y planificación del movimiento", Geometría discreta y computacional , 34 (4): 587–635, doi : 10.1007 / s00454-005-1184-0 , MR 2173930.
- Streinu, Ileana (2006), "Mecanismos de redibujado en paralelo, pseudo-triangulaciones y grafos cinéticos planos", Proc. En t. Symp. Graph Drawing (GD 2005) , Springer-Verlag, Lecture Notes in Computer Science 3843, págs. 421–433.