Pseudotriángulo

En la geometría plana euclidiana , un pseudotriángulo es el subconjunto simplemente conexo del plano que se encuentra entre tres conjuntos convexos tangentes entre sí . Por lo tanto, es una figura delimitada por tres lados curvados hacia adentro, formados por los límites de estos tres conjuntos convexos. Una pseudotriangulación es una partición de una región del plano en pseudotriángulos, y una pseudotriangulación puntiaguda es aquella en la que , en cada vértice, las aristas incidentes forman un ángulo menor que π.

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 utilizados 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 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 grafos y la transformación de formas. ^{[ 3 ]} Las pseudotriangulaciones puntiagudas surgen en la teoría de la rigidez como ejemplos de grafos planares mínimamente rígidos , ^{[ 4 ]} y en métodos para colocar guardias en relación con el teorema de la galería de arte . ^{[ 5 ]} El antimatroide de recubrimiento 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 análisis detallado de gran parte del material aquí tratado, véase Rote, Santos y Streinu (2008).

Pocchiola y Vegter ( 1996a , 1996b , 1996c ) definieron originalmente un pseudotriángulo como una región simplemente conexa del plano delimitada por tres curvas convexas suaves que son tangentes en sus extremos. ^{[ 7 ]} Sin embargo, trabajos posteriores han adoptado 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 conexa del plano, con 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 sobre el límite del pseudotriángulo. Por lo tanto, el pseudotriángulo es la región entre las envolventes convexas de estas tres curvas, y, de manera más general, cualquier conjunto de tres conjuntos convexos mutuamente tangentes forma un pseudotriángulo que se encuentra entre ellos. 

Para aplicaciones algorítmicas, es de particular interés caracterizar los 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 cóncavo un ángulo de exactamente π). Todo polígono debe tener al menos tres ángulos convexos porque el ángulo exterior total de un polígono es 2π, los ángulos convexos contribuyen con menos de π cada uno a este total, y los ángulos cóncavos contribuyen con cantidades nulas 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 son pseudotriángulos.

La envoltura convexa de cualquier pseudotriángulo es un triángulo. Las curvas que siguen el contorno del pseudotriángulo entre cada par de vértices convexos se encuentran dentro del triángulo o coinciden con uno de sus lados.

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 el mismo número de aristas y triángulos, esto no se aplica a 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 hasta 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 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. ^{[ 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 los datos de entrada se mueven, 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 total de arista mínima, y ​​proporcionan algoritmos de aproximación para este problema.

Una pseudotriangulación puntiaguda se define como una colección finita de segmentos de línea que no se cruzan, de modo que en cada vértice los segmentos incidentes abarcan un ángulo de como máximo π, y de modo que no se pueden añadir segmentos de línea entre dos vértices existentes sin que se pierda esta propiedad. Es evidente que una pseudotriangulación puntiaguda es una pseudotriangulación de su envolvente convexa: se pueden añadir todas las aristas de la envolvente convexa sin que se pierda la propiedad de abarcar ángulos, y todas las caras interiores deben ser pseudotriángulos, ya que de lo contrario se podría añadir un segmento de línea bitangente entre dos vértices de la cara.

Una pseudotriangulación puntiaguda con v vértices debe tener exactamente 2v − 3 aristas. ^{[ 9 ]} Esto se deduce mediante un sencillo 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 3f − 3 ángulos convexos entre aristas adyacentes. Cada arista es la arista en sentido horario para dos ángulos, por lo que hay un total de 2e ángulos , de los cuales todos excepto v son convexos. Por lo tanto, 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 e = 2v − 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 2k − 3 aristas. Por lo tanto, las pseudotriangulaciones puntiagudas satisfacen las condiciones que definen los grafos 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 consiguiente también las pseudotriangulaciones puntiagudas, son grafos mínimamente rígidos en dos dimensiones. Todo grafo de Laman planar puede representarse como una pseudotriangulación puntiaguda, aunque no todo dibujo planar de un grafo de Laman planar es una pseudotriangulación. ^{[ 10 ]}

Otra forma de encontrar una pseudotriangulación puntiaguda es vaciar 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 pueden formar de esta manera es el antimatroide de vaciado 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 diferentes, donde C _i denota el i- ésimo número de Catalan . Como consecuencia, muestran que los conjuntos de puntos con el menor número de pseudotriangulaciones 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. Los investigadores de geometría computacional también han proporcionado algoritmos para listar todas las pseudotriangulaciones de un conjunto de puntos en un pequeño tiempo por pseudotriangulación. ^{[ 11 ]}

• Curva deltoides
• Triángulo circular