En geometría del plano euclidiano , un pseudotriángulo ( pseudo-triángulo ) es el subconjunto simplemente conexo del plano que se encuentra entre tres conjuntos convexos tangentes entre sí . Una pseudotriangulación ( pseudo-triangulaciones ) es una partición de una región del plano en pseudotriángulos, y una pseudotriangulación puntiaguda es una pseudotriangulación en la que en cada vértice las aristas incidentes abarcan un ángulo de menos de π.
Aunque las palabras "pseudotriángulo" y "pseudotriangulación" se han utilizado con diversos significados en matemáticas durante mucho más tiempo, [1] los términos que se utilizan aquí fueron introducidos en 1993 por Michel Pocchiola y Gert Vegter en relación con el cálculo de relaciones de visibilidad y bitangentes entre obstáculos convexos en el plano. Las pseudotriangulaciones puntiagudas fueron consideradas por primera vez por Ileana Streinu (2000, 2005) como parte de su solución al problema de la regla del carpintero , una prueba de que cualquier trayectoria 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 de gráficos dinámicos 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 métodos para colocar protectores en relación con el teorema de la galería de arte . [5] El antimatroide de descascarado de un conjunto de puntos planos da lugar a pseudotriangulaciones puntiagudas, [6] aunque no todas las pseudotriangulaciones puntiagudas pueden surgir de esta manera.
Para un estudio detallado de gran parte del material analizado aquí, véase Rote, Santos y Streinu (2008).
(Pocchiola y Vegter 1996a, 1996b, 1996c) definieron originalmente un pseudotriángulo como una región simplemente conectada del plano delimitada por tres curvas convexas suaves que son tangentes en sus puntos finales. [7] Sin embargo, trabajos posteriores se han asentado en una definición más amplia que se aplica de manera más general a polígonos así como a 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 simplemente conectada del plano, 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 quedar completamente fuera o en el límite del pseudotriángulo. Por lo tanto, el pseudotriángulo es la región entre las envolturas convexas 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.
La envoltura convexa 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.
Una pseudotriangulación es una partición de una región del plano en pseudotriángulos. 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 la misma cantidad de aristas y triángulos, no sucede 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 pseudotriángulo y n aristas, o tantos como n − 2 pseudotriángulos y 2 n − 3 aristas.
Una pseudotriangulación mínima es una pseudotriangulación T tal que ningún subgrafo de T es una pseudotriangulación que cubra 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. [8]
Agarwal et al. (2002) describen estructuras de datos para mantener pseudotriangulaciones de puntos o polígonos en movimiento. Demuestran 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 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.
Una pseudotriangulación puntiaguda puede definirse como una colección finita de segmentos de línea que no se cruzan, de modo que en cada vértice los segmentos de línea incidentes abarcan un ángulo de π como máximo, y de modo que no se pueden agregar segmentos de línea entre dos vértices existentes mientras se preserva esta propiedad. No es difícil ver que una pseudotriangulación puntiaguda es una pseudotriangulación de su envoltura convexa: se pueden agregar todos los bordes de la envoltura convexa mientras se preserva la propiedad de abarcar á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 la cara.
Una pseudotriangulación puntiaguda con v vértices debe tener exactamente 2 v − 3 aristas. [9] Esto se deduce de un simple argumento de doble conteo 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 3 f − 3 ángulos convexos entre aristas adyacentes. Cada arista es la arista 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 excepto 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 la envoltura convexa 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 de k vértices de una pseudotriangulación puntiaguda puede completarse 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 a los grafos de Laman : tienen exactamente 2 v − 3 aristas, y sus subgrafos de k vértices tienen como máximo 2 k − 3 aristas. Los grafos de Laman, y por lo tanto también las pseudotriangulaciones puntiagudas, son grafos mínimamente rígidos en dos dimensiones. Todo grafo de Laman plano puede dibujarse como una pseudotriangulación puntiaguda, aunque no todo dibujo plano de un grafo de Laman plano es una pseudotriangulación. [10]
Otra forma de encontrar una pseudotriangulación puntiaguda es descascarar un conjunto de puntos; es decir, eliminar los vértices de la envoltura 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 descascarado del conjunto de puntos, y el conjunto de aristas de las envolturas convexas 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 puntiagudas se pueden formar de esta manera.
Aichholzer et al. (2004) muestran que un conjunto de n puntos, h de los cuales pertenecen a la envoltura convexa del conjunto, debe tener al menos C h −2 ×3 n − h pseudotriangulaciones puntiagudas diferentes, donde C i denota el i ésimo número de Catalan . Como consecuencia, muestran que los conjuntos de puntos con menos pseudotriangulaciones puntiagudas 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 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. [11]