Las denominaciones extensor geométrico (geometric spanner en inglés), grafo de extensor o simplemente extensor se introdujeron inicialmente en la terminología de la teoría de grafos para describir un grafo ponderado sobre un conjunto de puntos definidos como vértices, para el que existe un camino entre cualquier par de vértices de acuerdo con un parámetro fijo dado . Un camino se define como un camino a través del grafo con un peso como máximo de veces la distancia espacial entre sus extremos. El parámetro se denomina factor de estiramiento o factor de dilatación del extensor.

En geometría computacional, el concepto fue discutido por primera vez por L.P. Chew en 1986, aunque el término extensor no se utilizó en el artículo original.

La noción de grafos extensores es conocido en la teoría de grafos: los -extensores son subgrafos extensores 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 extensores geométricos son extensores de grafos completos embebidos en el plano con pesos de arista iguales a las distancias entre los vértices incrustados en la métrica correspondiente.

Los extensores pueden usarse en geometría computacional para resolver algunos problemas de proximidad. También se han encontrado aplicaciones en otras áreas, como en planificación de movimiento, redes de telecomunicaciones, fiabilidad de redes, o en la optimización de itinerancia en redes de celdas entre otras posibilidades.

Diferentes algoritmos de extensión y medidas de calidad Existen diferentes medidas que se pueden utilizar para analizar la calidad de un conector. 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 óptimos asintóticos para estas medidas son aristas, peso y grado máximo (donde MST denota el peso del árbol recubridor mínimo).

Se sabe que encontrar un conector en el plano euclídeo con una dilatación mínima sobre n puntos con como máximo m aristas es NP-hard.

Existen muchos algoritmos de extensión que destacan en diferentes medidas de calidad. Los algoritmos rápidos incluyen el grafo de descomposición de pares bien separados (WSPD) y el grafo theta, que generan grafos con un número lineal de aristas en tiempo . Si se requiere un mejor peso y grado de los vértices, con un algoritmo de grafo voraz se puede calcular en tiempo casi cuadrático.

Grafo theta

El grafo theta o grafo pertenece a la familia de grafos basados en conos. El método básico de construcción consiste en dividir el espacio alrededor de cada vértice en un conjunto de conos, que a su vez separan los vértices restantes del grafo. Al igual que los grafos de Yao, un grafo contiene como máximo una arista por cono, y su diferencia radica en cómo se selecciona dicha arista. Mientras que en los grafos de Yao se selecciona el vértice más cercano según el espacio métrico del grafo, en el grafo se define un rayo fijo contenido dentro de cada cono (convencionalmente la bisectriz del cono) y se selecciona el vecino más cercano con respecto a las proyecciones ortogonales a dicho rayo.

Grafo de extensión voraz

El grafo de extensió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 de extensión. Los algoritmos que calculan este grafo se denominan algoritmos de extensión voraz. De su construcción se deduce trivialmente que el grafo de extensión voraz es un grafo de extensión.

El algoritmo de extensión voraz se describió por primera vez en la tesis doctoral de Gautam Das y en una ponencia de un congreso, seguido de un artículo en una revista de Ingo Althöfer et al.. Estas fuentes también atribuyen a Marshall Bern (inédito) el descubrimiento independiente de la misma construcción.

El algoritmo de extensión voraz alcanza un número de aristas, un peso total y un grado máximo de vértice asintóticamente óptimos, y también ofrece el mejor rendimiento en estas medidas en la práctica.

Puede construirse en tiempo utilizando un tiempo .

Triangulación de Delaunay El principal resultado de Chew fue que, para un conjunto de puntos en el plano, existe una triangulación de este conjunto tal que, para dos puntos cualesquiera, existe un camino en las aristas de la triangulación con una longitud como máximo veces la distancia euclídea entre los dos puntos. Este resultado se aplicó en la planificación de movimiento para encontrar aproximaciones razonables de los caminos más cortos entre obstáculos.

La mejor cota superior conocida para la triangulación de Delaunay euclídea es un -extensor para sus vértices.

La cota inferior se ha incrementado de a un valor ligeramente superior, 1,5846.

Descomposición de pares bien separados

Un extensor puede construirse a partir de una descomposición de pares bien separados de la siguiente manera. Constrúyase el grafo con el conjunto de puntos como conjunto de vértices y, para cada par en una descomposición en pares bien separada (WSPD), añadir una arista desde un punto arbitrario a un punto arbitrario . Téngase en cuenta que el grafo resultante tiene un número lineal de aristas, ya que una WSPD tiene un número lineal de pares.

Es posible obtener un valor arbitrario para eligiendo adecuadamente el parámetro de separación de la descomposición en pares bien separados.

Referencias .

.

.

Categoría:Algoritmos geométricos Categoría:Grafos geométricos