Llave geométrica codiciosa

En geometría computacional , una llave geométrica voraz es un grafo no dirigido cuyas distancias se aproximan a las distancias euclidianas entre un conjunto finito de puntos en un espacio euclidiano . Los vértices del grafo representan estos puntos. Los bordes de la llave se seleccionan mediante un algoritmo voraz que incluye un borde siempre que sus dos puntos finales no estén conectados por un camino corto de bordes más cortos. La llave voraz se describió por primera vez en la tesis doctoral de Gautam Das ^[1] y el artículo de conferencia ^[2] y el artículo de revista posterior de Ingo Althöfer et al. ^[3] Estas fuentes también acreditaron a Marshall Bern (inédito) con el descubrimiento independiente de la misma construcción.

Los extensores geométricos voraces tienen un grado acotado , un número total lineal de aristas y un peso total cercano al del árbol de expansión mínimo euclidiano . Aunque los métodos de construcción conocidos para ellos son lentos, se conocen algoritmos de aproximación rápida con propiedades similares. ^[4]

El extensor geométrico voraz se determina a partir de una entrada que consiste en un conjunto de puntos y un parámetro . El objetivo es construir un grafo cuyas distancias de ruta más cortas sean, como máximo, las distancias geométricas entre pares de puntos. Puede construirse mediante un algoritmo voraz que añade aristas una a la vez al grafo, comenzando desde un grafo sin aristas con los puntos como sus vértices. Se consideran todos los pares de puntos, en orden ordenado (ascendente) por sus distancias, comenzando con el par más cercano . Para cada par de puntos, el algoritmo prueba si el grafo construido hasta ahora ya contiene una ruta desde a con longitud como máximo . Si no, la arista con longitud se añade al grafo. Por construcción, el grafo resultante es un extensor geométrico con factor de estiramiento como máximo . ^[3]${\displaystyle t\geq 1}$${\estilo de visualización t}$${\estilo de visualización (u,v)}$${\estilo de visualización u}$${\estilo de visualización v}$${\displaystyle t\cdot d(u,v)}$${\estilo de visualización uv}$${\displaystyle d(u,v)}$${\estilo de visualización t}$

Una implementación ingenua de este método tomaría tiempo en entradas con puntos. Esto se debe a que las consideraciones para cada uno de los pares de puntos involucran una instancia del algoritmo de Dijkstra para encontrar un camino más corto en un gráfico con aristas. Utiliza el espacio para almacenar la lista ordenada de pares de puntos. Los algoritmos más cuidadosos pueden construir el mismo gráfico en tiempo , ^[5] o en espacio . ^[6] Una construcción para una variante del greedy spanner que utiliza la agrupación de gráficos para aproximar rápidamente las distancias de los gráficos se ejecuta en el tiempo en espacios euclidianos de cualquier dimensión acotada, y puede producir spanners con (aproximadamente) las mismas propiedades que los spanners greedy. ^{[7] [8]} El mismo método se puede extender a espacios con dimensión de duplicación acotada . ^[4]${\displaystyle O(n^{3}\log n)}$${\estilo de visualización n}$$Estilo de visualización O(n^{2})}$${\displaystyle O(n)}$$Estilo de visualización O(n^{2})}$${\displaystyle O(n^{2}\log n)}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

La misma construcción codiciosa produce llaves en espacios métricos arbitrarios , pero en espacios euclidianos tiene buenas propiedades, algunas de las cuales no se cumplen de manera más general. ^[4]

El algoritmo de construcción greedy spanner geométrico en cualquier espacio métrico siempre contiene el árbol de expansión mínimo de su entrada, porque el algoritmo de construcción greedy sigue el mismo orden de inserción de aristas que el algoritmo de Kruskal para árboles de expansión mínimos. Si el algoritmo de construcción greedy spanner y el algoritmo de Kruskal se ejecutan en paralelo, considerando los mismos pares de vértices en el mismo orden, cada arista agregada por el algoritmo de Kruskal también será agregada por el algoritmo de construcción greedy spanner, porque los puntos finales de la arista no estarán ya conectados por un camino. En el caso límite cuando es lo suficientemente grande (por ejemplo , donde es el número de vértices en el gráfico), los dos algoritmos producen la misma salida. ^[3]${\displaystyle t}$${\displaystyle t>n}$${\displaystyle n}$

En espacios euclidianos de dimensión acotada, para cualquier constante , los -spanners geométricos voraces en conjuntos de puntos tienen grado acotado , lo que implica que también tienen aristas. ^{[9] [10] [7]} Esta propiedad no se extiende ni siquiera a espacios métricos de buen comportamiento: existen espacios con dimensión duplicada acotada donde el -spanner voraz tiene grado de vértice ilimitado. ^{[4] [11] [12]} Sin embargo, en tales espacios el número de aristas sigue siendo . ^[4]${\displaystyle t}$${\displaystyle t}$${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n)}$

Los árboles de expansión geométricos voraces en espacios euclidianos de dimensión acotada también tienen un peso total como máximo de una constante multiplicada por el peso total del árbol de expansión mínimo euclidiano . ^{[9] [10] [7]} Esta propiedad sigue siendo cierta en espacios de dimensión duplicada acotada. ^[4]