Llave geométrica

Grafo no dirigido ponderado con distancias gráficas acotadas linealmente con respecto a las distancias euclidianas

Un grafo de llave geométrica o grafo de llave t o grafo de llave t se introdujo inicialmente como un grafo ponderado sobre un conjunto de puntos como sus vértices para los cuales existe un camino t entre cualquier par de vértices para un parámetro fijo t . Un camino t se define como un camino a través del grafo con un peso de como máximo t veces la distancia espacial entre sus puntos finales. El parámetro t se denomina factor de estiramiento o factor de dilatación del grafo de llave. ^[1]

En geometría computacional , el concepto fue discutido por primera vez por LP Chew en 1986, ^[2] aunque el término "llave" no se utilizó en el artículo original.

El concepto de grafos spanners ya se conocía en la teoría de grafos : los t -spanners son subgrafos de grafos que abarcan la totalidad de los grafos y que tienen propiedades de dilatación similares, donde las distancias entre los vértices de los grafos se definen en términos de teoría de grafos . Por lo tanto, los grafos spanners geométricos son grafos spanners de grafos completos incrustados en el plano con pesos de aristas iguales a las distancias entre los vértices incrustados en la métrica correspondiente.

Las llaves inglesas se pueden utilizar en geometría computacional para resolver algunos problemas de proximidad . También han encontrado aplicaciones en otras áreas, como en la planificación de movimiento , redes de telecomunicaciones , confiabilidad de red, optimización de roaming en redes móviles , etc.

Diferentes llaves y medidas de calidad

Existen diferentes medidas que se pueden utilizar para analizar la calidad de una llave. Las medidas más comunes son el número de aristas, el peso total y el grado máximo de vértice . Los valores asintóticamente óptimos para estas medidas son las aristas, el peso y el grado máximo (aquí MST denota el peso del árbol de expansión mínimo ). ${\displaystyle O(n)}$ ${\displaystyle O(MST)}$ ${\displaystyle O(1)}$

Se sabe que encontrar una llave en el plano euclidiano con una dilatación mínima sobre n puntos con m aristas como máximo es una operación NP-difícil . ^[3]

Existen muchos algoritmos de spanner que se destacan en diferentes medidas de calidad. Los algoritmos rápidos incluyen el spanner WSPD y el gráfico Theta , que construyen spanners con un número lineal de aristas en el tiempo. Si se requiere un mejor peso y grado de vértice, el spanner Greedy se puede calcular en un tiempo casi cuadrático. ${\displaystyle O(n\log n)}$

El gráfico Theta

El grafo Theta o -grafo pertenece a la familia de los conos de expansión. 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 el vecino más cercano con respecto a las proyecciones ortogonales a ese rayo. ${\displaystyle \Theta }$ ${\displaystyle \Theta }$ ${\displaystyle \Theta }$

La llave inglesa codiciosa

El grafo voraz o grafo voraz se define como el grafo resultante de sumar repetidamente una arista entre el par de puntos más cercano sin una ruta t . Los algoritmos que calculan este grafo se conocen como algoritmos de grafo voraz. De la construcción se deduce trivialmente que el grafo voraz es un grafo voraz .

La llave inglesa voraz fue descrita por primera vez en la tesis doctoral de Gautam Das ^[4] y en un artículo de conferencia ^[5] y un artículo de revista posterior de Ingo Althöfer et al ^[6] . Estas fuentes también atribuyeron a Marshall Bern (inédito) el descubrimiento independiente de la misma construcción.

La llave inglesa voraz logra un número de aristas, un peso total y un grado de vértice máximos asintóticamente óptimos y, además, tiene el mejor rendimiento en estas medidas en la práctica. Se puede construir en el tiempo utilizando el espacio. ^[7] ${\displaystyle O(n^{2}\log n)}$ ${\displaystyle O(n^{2})}$

La triangulación de Delaunay

El resultado principal de Chew fue que para un conjunto de puntos en el plano existe una triangulación de este conjunto de puntos tal que para dos puntos cualesquiera existe un camino a lo largo de los bordes de la triangulación con una longitud como máximo igual a la distancia euclidiana entre los dos puntos. El resultado se aplicó en la planificación del movimiento para encontrar aproximaciones razonables de los caminos más cortos entre obstáculos. ${\displaystyle {\sqrt {10}}}$

El mejor límite superior conocido para la triangulación euclidiana de Delaunay es que es un -spanner para sus vértices. ^[8] El límite inferior se ha incrementado de a justo por encima de eso, a 1,5846. ^[9] ${\displaystyle 1.998}$ ${\displaystyle {{\pi }/2}}$

Descomposición de pares bien separados

Se puede construir una llave a partir de una descomposición de pares bien separados de la siguiente manera. Construya el gráfico con el conjunto de puntos como conjunto de vértices y para cada par en un WSPD, agregue una arista desde un punto arbitrario a un punto arbitrario . Tenga en cuenta que el gráfico resultante tiene un número lineal de aristas porque un WSPD tiene un número lineal de pares. ^[10] ${\displaystyle S}$ ${\displaystyle \{A,B\}}$ ${\displaystyle a\in A}$ ${\displaystyle b\in B}$

Es posible obtener un valor arbitrario eligiendo el parámetro de separación de la descomposición de pares bien separados en consecuencia. ${\displaystyle t}$

Referencias

1. Narasimhan, Giri; Smid, Michiel (2007), Redes de llaves geométricas , Cambridge University Press , ISBN 978-0-521-81513-0.
2. Chew, L. Paul (1986), "Existe un gráfico planar casi tan bueno como el gráfico completo", Proc. 2nd Annual Symposium on Computational Geometry , pp. 169–177, doi :10.1145/10515.10534, S2CID  42010166.
3. Klein, Rolf; Kutz, Martin (2007), "El cálculo de grafos geométricos de mínima dilatación es NP-difícil", en Kaufmann, Michael; Wagner, Dorothea (eds.), Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Alemania, 2006 , Lecture Notes in Computer Science , vol. 4372, Springer Verlag , págs. 196–207, doi :10.1007/978-3-540-70904-6, ISBN 978-3-540-70903-9.
4. Das, Gautam (1990), Esquemas de aproximación en geometría computacional (tesis doctoral), Universidad de Wisconsin-Madison, OCLC  22935858
5. Althöfer, Ingo ; Das, Gautam ; Dobkin, David ; Joseph, Deborah (1990), "Generación de spanners dispersos para gráficos ponderados", SWAT 90 , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 26–37, CiteSeerX 10.1.1.158.2241 , doi :10.1007/3-540-52846-6_75, ISBN  978-3-540-52846-3, consultado el 16 de marzo de 2021
6. Althöfer, Ingo ; Das, Gautam ; Dobkin, David ; Joseph, Deborah ; Soares, José (1993), "Sobre los extensores dispersos de grafos ponderados", Geometría discreta y computacional , 9 (1): 81–100, doi : 10.1007/BF02189308 , MR  1184695
7. Bose, P. ; Carmi, P.; Farshi, M.; Maheshwari, A.; Smid, M. (2010), "Cálculo de la llave inglesa voraz en tiempo casi cuadrático.", Algorithmica , 58 (3): 711–729, doi :10.1007/s00453-009-9293-4, S2CID  8068690
8. Xia, Ge (2013), "El factor de estiramiento de la triangulación de Delaunay es menor que 1,998", SIAM Journal on Computing , 42 (4): 1620–1659, arXiv : 1103.4361 , doi :10.1137/110832458, MR  3082502, S2CID  6646528
9. Bose, Prosenjit ; Devroye, Luc; Loeffler, Maarten; Snoeyink, Jack; Verma, Vishal (2009), "La relación de expansión de la triangulación de Delaunay es mayor que ", Conferencia canadiense sobre geometría computacional (PDF) , Vancouver, págs. 165-167 ${\displaystyle {\pi /2}}${{citation}}: CS1 maint: location missing publisher (link)
10. Callahan, PB; Kosaraju, SR (enero de 1995), "Una descomposición de conjuntos de puntos multidimensionales con aplicaciones a los vecinos más cercanos y a los campos bonetales de cuerpos", Journal of the ACM , 42 (1): 67–90, doi : 10.1145/200836.200853 , S2CID  1818562 ${\displaystyle k}$ ${\displaystyle n}$