Gráfica theta

Tipo de gráfico de llave inglesa geométrica

En geometría computacional , el grafo Theta , o -grafo , es un tipo de llave geométrica similar a un grafo Yao . El método básico de construcción implica dividir el espacio alrededor de cada vértice en un conjunto de conos , que a su vez dividen los vértices restantes del grafo. Al igual que los grafos Yao, un -grafo contiene como máximo una arista por cono; en lo que difieren es en cómo se selecciona esa arista. Mientras que los grafos Yao seleccionarán el vértice más cercano según el espacio métrico del grafo, el -grafo define un rayo fijo contenido dentro de cada cono (convencionalmente la bisectriz del cono) y selecciona al vecino más cercano con respecto a las proyecciones ortogonales a ese rayo. El grafo resultante exhibe varias buenas propiedades de llave. ^[1] ${\displaystyle \Theta }$ ${\displaystyle \Theta }$ ${\displaystyle \Theta }$

${\displaystyle \Theta }$Los -grafos fueron descritos por primera vez por Clarkson ^[2] en 1987 e independientemente por Keil ^[3] en 1988.

Construcción

Ejemplo de cono de un -grafo que emana de una línea de proyección ortogonal ${\displaystyle \Theta }$ ${\displaystyle p}$ ${\displaystyle l}$

${\displaystyle \Theta }$-Los grafos se especifican con unos pocos parámetros que determinan su construcción. El parámetro más obvio es , que corresponde al número de conos de ángulos iguales que dividen el espacio alrededor de cada vértice. En particular, para un vértice , un cono sobre puede imaginarse como dos rayos infinitos que emanan de él con un ángulo entre ellos. Con respecto a , podemos etiquetar estos conos como a través de un patrón en sentido antihorario desde , que convencionalmente se abre de modo que su bisectriz tiene un ángulo 0 con respecto al plano. A medida que estos conos dividen el plano, también dividen el conjunto de vértices restante del grafo (asumiendo la posición general ) en los conjuntos a través de , nuevamente con respecto a . Cada vértice en el grafo tiene el mismo número de conos en la misma orientación, y podemos considerar el conjunto de vértices que caen en cada uno. ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \theta =2\pi /k}$ ${\displaystyle p}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{k}}$ ${\displaystyle C_{1}}$ ${\displaystyle V_{1}}$ ${\displaystyle V_{k}}$ ${\displaystyle p}$

Considerando un solo cono, necesitamos especificar otro rayo que emana de , que etiquetaremos como . Para cada vértice en , consideramos la proyección ortogonal de cada uno sobre . Supongamos que es el vértice con la proyección más cercana, entonces se agrega la arista al gráfico. Esta es la principal diferencia con los gráficos Yao, que siempre seleccionan el vértice más cercano; en la imagen de ejemplo, un gráfico Yao incluiría la arista en su lugar. ${\displaystyle p}$ ${\displaystyle l}$ ${\displaystyle V_{i}}$ ${\displaystyle v\in V_{i}}$ ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle \{p,r\}}$ ${\displaystyle \{p,q\}}$

La construcción de un -grafo es posible con un algoritmo de línea de barrido en el tiempo. ^[1] ${\displaystyle \Theta }$ ${\displaystyle O(n\log {n})}$

Propiedades

${\displaystyle \Theta }$-Los gráficos muestran varias buenas propiedades de llave geométrica .

Cuando el parámetro es una constante, el gráfico es un extensor disperso. Como cada cono genera como máximo una arista por cono, la mayoría de los vértices tendrán un grado pequeño y el gráfico general tendrá como máximo aristas. ${\displaystyle k}$ ${\displaystyle \Theta }$ ${\displaystyle k\cdot n=O(n)}$

El factor de estiramiento entre cualquier par de puntos en una llave inglesa se define como la relación entre su distancia en el espacio métrico y su distancia dentro de la llave inglesa (es decir, desde los bordes siguientes de la llave inglesa). El factor de estiramiento de toda la llave inglesa es el factor de estiramiento máximo sobre todos los pares de puntos dentro de ella. Recordemos de lo anterior que , entonces cuando , el -grafo tiene un factor de estiramiento de como máximo . ^[1] Si se elige que la línea de proyección ortogonal en cada cono sea la bisectriz, entonces para , la relación de expansión es como máximo . ^[4] ${\displaystyle \theta =2\pi /k}$ ${\displaystyle k\geq 9}$ ${\displaystyle \Theta }$ ${\displaystyle 1/(\cos \theta -\sin \theta )}$ ${\displaystyle l}$ ${\displaystyle k\geq 7}$ ${\displaystyle 1/(1-2\sin(\pi /k))}$

Para , el -grafo forma un grafo de vecino más próximo . Para , es fácil ver que el grafo está conectado, ya que cada vértice se conectará con algo a su izquierda y algo a su derecha, si existen. Para ^[5] , ^[6] , ^[7] , ^[8] y , ^[4] se sabe que el -grafo está conectado. Muchos de estos resultados también dan límites superiores y/o inferiores en sus razones de expansión. ${\displaystyle k=1}$ ${\displaystyle \Theta }$ ${\displaystyle k=2}$ ${\displaystyle k=3}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle 6}$ ${\displaystyle \geq 7}$ ${\displaystyle \Theta }$

Cuando es un número par, podemos crear una variante del -grafo conocida como el semigrafo , donde los conos mismos se dividen en conjuntos pares e impares de manera alternada, y las aristas solo se consideran en los conos pares (o, solo en los conos impares). Se sabe que los semigrafos tienen algunas propiedades propias muy interesantes. Por ejemplo, se sabe que el semigrafo (y, en consecuencia, el -grafo, que es simplemente la unión de dos semigrafos complementarios ) es un 2-spanner. ^[8] ${\displaystyle k}$ ${\displaystyle \Theta _{k}}$ ${\displaystyle \Theta _{k}}$ ${\displaystyle \Theta _{k}}$ ${\displaystyle \Theta _{6}}$ ${\displaystyle \Theta _{6}}$ ${\displaystyle \Theta _{6}}$

Software para dibujar gráficos Theta

• Una herramienta escrita en Java
• Llaves basadas en conos en la biblioteca de algoritmos de geometría computacional (CGAL)

Véase también

• Gráfico de Yao
• Gráfico de Semi-Yao
• llave geométrica

Referencias

1. Narasimhan, Giri; Smid, Michiel (2007), Redes de llaves geométricas , Cambridge University Press , ISBN 978-0-521-81513-0.
2. K. Clarkson. 1987. Algoritmos de aproximación para la planificación del movimiento por la ruta más corta. En Actas del decimonoveno simposio anual de la ACM sobre teoría de la computación (STOC '87), Alfred V. Aho (Ed.). ACM, Nueva York, NY, EE. UU., 56–65.
3. Keil, J. (1988). Aproximación del gráfico euclidiano completo. SWAT 88, 208–213.
4. Ruppert, J., y Seidel, R. (1991). Aproximación del grafo euclidiano completo de dimensión d . En Proc. 3rd Canad. Conf. Comput. Geom (pp. 207–210).
5. Aichholzer, Oswin; Bae, Sang Won; Barba, Luis; Bosé, Prosenjit; Korman, Matías; van Renssen, André; Taslakian, Perouz; Verdonschot, Sander (octubre de 2014), "Theta-3 está conectado", Computational Geometry , 47 (9): 910–917, arXiv : 1404.7186 , doi : 10.1016/j.comgeo.2014.05.001{{citation}}: CS1 maint: date and year (link)
6. Barba, Luis; Bosé, Prosenjit ; De Carufel, Jean-Lou; van Renssen, André; Verdonschot, Sander (2013), "Sobre el factor de estiramiento del gráfico theta-4", Algoritmos y estructuras de datos , Lecture Notes in Computer Science, vol. 8037, Heidelberg: Springer, págs. 109-120, arXiv : 1303.5473 , doi : 10.1007/978-3-642-40104-6_10 , ISBN 978-3-642-40103-9, Sr.  3126350.
7. Bosé, Prosenjit ; Morín, Pat ; van Renssen, André; Verdonschot, Sander (2015), "El gráfico θ ₅ es una llave inglesa", Geometría computacional , 48 (2): 108–119, arXiv : 1212.0570 , doi : 10.1016/j.comgeo.2014.08.005 , MR  3260251.
8. Bonichon, N., Gavoille, C., Hanusse, N., & Ilcinkas, D. (2010). Conexiones entre grafos theta, triangulaciones de Delaunay y superficies ortogonales. En Graph Theoretic Concepts in Computer Science (pp. 266–278). Springer Berlin/Heidelberg.