Pseudotriangulo
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 π.
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 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 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.
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 regiones delimitadas por curvas suaves, y eso 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 que π 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.
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.
