En geometría computacional , el gráfico Theta , o-graph , es un tipo de llave geométrica similar a un gráfico 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 gráfico. Como Yao Graphs, un-El gráfico contiene como máximo un borde por cono; donde difieren es cómo se selecciona ese borde. Mientras que Yao Graphs seleccionará el vértice más cercano de acuerdo con el espacio métrico del gráfico, elEl gráfico define un rayo fijo contenido dentro de cada cono (convencionalmente la bisectriz del cono) y selecciona el vecino más cercano con respecto a las proyecciones ortogonales de ese rayo. El gráfico resultante presenta varias buenas propiedades de llave. [1]
-Las gráficas fueron descritas por primera vez por Clarkson [2] en 1987 e independientemente por Keil [3] en 1988.
Construcción
-Los gráficos 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 se puede imaginar como dos rayos infinitos que emanan de él con un ángulo entre ellos. Con respecto a, podemos etiquetar estos conos como mediante en un patrón en sentido antihorario desde , que se abre convencionalmente de modo que su bisectriz tenga 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 gráfico (asumiendo la posición general ) en los conjuntos. mediante , de nuevo con respecto a . Cada vértice del gráfico obtiene el mismo número de conos en la misma orientación y podemos considerar el conjunto de vértices que caen en cada uno.
Considerando un solo cono, necesitamos especificar otro rayo que emana de , que etiquetaremos . Por cada vértice en, consideramos la proyección ortogonal de cada sobre . Suponer que es el vértice con la proyección más cercana, luego el borde se agrega al gráfico. Ésta es la principal diferencia con los gráficos de Yao, que siempre seleccionan el vértice más cercano; en la imagen de ejemplo, un gráfico Yao incluiría el borde en lugar de.
Construcción de un -graph es posible con un algoritmo de línea de barrido enhora. [1]
Propiedades
-Las gráficas exhiben varias buenas propiedades de llave geométrica .
Cuando el parámetro es una constante, la -El gráfico es una llave inglesa escasa. Como cada cono genera como máximo un borde por cono, la mayoría de los vértices tendrán un grado pequeño y el gráfico general tendrá como máximo bordes.
El factor de estiramiento entre cualquier par de puntos en una llave se define como la relación entre su distancia espacial métrica y su distancia dentro de la llave (es decir, desde los bordes siguientes de la llave). El factor de estiramiento de toda la llave es el factor de estiramiento máximo sobre todos los pares de puntos dentro de ella. Recuerda desde arriba que, entonces cuando , la -El gráfico tiene un factor de estiramiento de como máximo . [1] Si la línea de proyección ortogonal en cada cono se elige para ser la bisectriz, luego para , la relación de expansión es como máximo . [4]
Para , la -graph forma un gráfico vecino más cercano . Para, es fácil ver que la gráfica está conectada, 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] elSe sabe que el gráfico está conectado. Muchos de estos resultados también dan límites superiores y / o inferiores en sus proporciones de expansión.
Cuándo es un número par, podemos crear una variante del -grafa conocida como la mitad--graph , donde los conos de sí mismos se dividen en incluso y impares conjuntos de una manera alternante, y los bordes sólo se consideran en los conos incluso (o, sólo los conos impares). Mitad--Los gráficos son conocidos por tener algunas propiedades propias muy agradables. Por ejemplo, la mitad-Gráfico (y, en consecuencia, el -grafa, que es solo la unión de dos mitades complementarias--graphs) se sabe que es una llave de dos llaves. [8]
Software para dibujar gráficos Theta
Ver también
Referencias
- ^ a b c Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks , Cambridge University Press , ISBN 0-521-81513-4.
- ^ K. Clarkson. 1987. Algoritmos de aproximación para la planificación del movimiento de la trayectoria más corta. En Actas del decimonoveno simposio anual de ACM sobre teoría de la computación (STOC '87), Alfred V. Aho (Ed.). ACM, Nueva York, NY, EE. UU., 56–65.
- ^ Keil, J. (1988). Aproximación del gráfico euclidiano completo. SWAT 88, 208-213.
- ↑ a b Ruppert, J. y Seidel, R. (1991). Aproximación del gráfico euclidiano completo d- dimensional. En Proc. 3rd Canad. Conf. Computación. Geom (págs. 207-210).
- ^ Oswin Aichholzer, Sang Won Bae, Luis Barba, Prosenjit Bose, Matias Korman, André van Renssen, Perouz Taslakian, Sander (2014). Theta-3 está conectado. En geometría computacional: teoría y aplicaciones (volumen 47, número 9, octubre de 2014, páginas 910-917). https://doi.org/10.1016/j.comgeo.2014.05.001
- ^ Barba, Luis; Bose, 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, 8037 , Heidelberg: Springer, págs. 109-120, arXiv : 1303.5473 , doi : 10.1007 / 978-3-642-40104-6_10 , MR 3126350.
- ^ Bose, Prosenjit ; Morin, Pat ; van Renssen, André; Verdonschot, Sander (2015), "El gráfico θ 5 es una llave inglesa", Computational Geometry , 48 (2): 108-119, arXiv : 1212.0570 , doi : 10.1016 / j.comgeo.2014.08.005 , MR 3260251.
- ↑ a b Bonichon, N., Gavoille, C., Hanusse, N. y Ilcinkas, D. (2010). Conexiones entre theta-grafos, triangulaciones de Delaunay y superficies ortogonales. En Graph Theoretic Concepts in Computer Science (págs. 266–278). Springer Berlín / Heidelberg.