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

[editar]

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

[editar]

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

[editar]
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 = 2ev. Combinando esto con la ecuación de Euler fe + 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 Ch−2×3nh pseudotriangulaciones agudas diferentes, donde Ci 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

[editar]

Referencias

[editar]
  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. a b 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

[editar]