llave geométrica

Un grafo t- expansor geométrico o t - expansor se introdujo inicialmente como un grafo ponderado sobre un conjunto de puntos como vértices, para el cual 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 como máximo t veces la distancia espacial entre sus extremos. El parámetro t se denomina factor de estiramiento o factor de dilatación del grafo. ^{[ 1 ]}

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

El concepto de grafos expansores es conocido en la teoría de grafos : los t -expandores son subgrafos expansores de grafos con una propiedad de dilatación similar, donde las distancias entre los vértices del grafo se definen en términos de la teoría de grafos . Por lo tanto, los expansores geométricos son expansores de grafos completos incrustados en el plano con pesos de arista iguales a las distancias entre los vértices incrustados en la métrica correspondiente.

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

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

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

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

El gráfico Theta o${\displaystyle \Theta }$-graph pertenece a la familia de los expansores basados ​​en conos. El método básico de construcción implica particionar el espacio alrededor de cada vértice en un conjunto de conos, que a su vez particionan los vértices restantes del grafo. Al igual que los grafos Yao , un${\displaystyle \Theta }$-El grafo contiene como máximo una arista por cono; donde difieren es en cómo se selecciona esa arista. Mientras que los grafos Yao seleccionarán el vértice más cercano de acuerdo con el espacio métrico del grafo, el${\displaystyle \Theta }$-El 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 a ese rayo.

El grafo voraz, o grafo de expansión voraz, se define como el grafo resultante de añadir repetidamente una arista entre el par de puntos más cercanos sin un camino t . Los algoritmos que calculan este grafo se denominan algoritmos de expansión voraz. De su construcción se deduce fácilmente que el grafo voraz es un grafo de expansión t .

La llave inglesa codiciosa fue descrita por primera vez en la tesis doctoral de Gautam Das ^{[ 4 ]} y en un artículo de congreso ^{[ 5 ]} , y posteriormente en un artículo de revista de Ingo Althöfer et al . ^{[ 6 ]} . Estas fuentes también atribuyen a Marshall Bern (sin publicar) el descubrimiento independiente de la misma construcción.

El algoritmo greedy spanner logra un número de aristas, un peso total y un grado máximo de vértice asintóticamente óptimos, y también se desempeña mejor en estas medidas en la práctica. Se puede construir en${\displaystyle O(n^{2}\log n)}$tiempo usando${\displaystyle O(n^{2})}$espacio. ^{[ 7 ]}

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

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

Un conector puede construirse a partir de una descomposición de pares bien separados de la siguiente manera. Construya el grafo con el conjunto de puntos.${\displaystyle S}$como conjunto de vértices y para cada par${\displaystyle \{A,B\}}$En un WSPD, agregue una arista desde un punto arbitrario.${\displaystyle a\in A}$hasta un punto arbitrario${\displaystyle b\in B}$. Nótese que el grafo resultante tiene un número lineal de aristas porque un WSPD tiene un número lineal de pares. ^{[ 10 ]}

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