En geometría computacional, un extensor geométrico voraz es un grafo cuyas distancias se aproximan a las distancias euclídeas entre un conjunto finito de puntos en un espacio euclídeo. Los vértices del grafo representan estos puntos. Las aristas del extensor se seleccionan mediante un algoritmo voraz que incluye una arista siempre que sus dos extremos no estén conectados por otro camino de aristas cuya longitud sea inferior a veces la distancia entre los dos puntos. Se describió por primera vez en la tesis doctoral de Gautam Das y en la ponencia de un congreso, así como en un artículo posterior de Ingo Althöfer et al. Estas fuentes también atribuyen a Marshall Bern (inédito) el descubrimiento independiente de la misma construcción.
Los extensores geométricos voraces tienen grado acotado, un número total de aristas lineal y un peso total cercano al del árbol de extensión mínima euclídea. Aunque los métodos de construcción conocidos para ellos son lentos, se conocen algoritmos de aproximación rápidos con propiedades similares.
Construcción El algoritmo de extensión geométrica voraz se determina a partir de una entrada que consiste en un conjunto de puntos y de un parámetro . El objetivo es construir un grafo cuyas distancias de camino más corto sean como máximo veces la distancia geométrica entre pares de puntos. Puede construirse mediante un algoritmo voraz que añade aristas una a una al grafo, comenzando desde un grafo nulo con los puntos como vértices. Se consideran todos los pares de puntos, ordenados (de forma ascendente) según sus distancias, comenzando con el par más cercano. Para cada par de puntos, el algoritmo comprueba si el grafo construido hasta el momento ya contiene un camino de a con una longitud como máximo . Si no, se añade la arista con longitud al grafo.
Por construcción, el grafo resultante es un extensor geométrico con factor de estiramiento como máximo .
Una implementación ingenua de este método tardaría tiempo con puntos de entrada. Esto se debe a que las consideraciones para cada uno de los pares de puntos implican una instancia del algoritmo de Dijkstra para encontrar el camino más corto en un grafo con aristas. Utiliza espacio para almacenar la lista ordenada de pares de puntos. Algoritmos más cuidadosos pueden construir el mismo grafo en tiempo , o en tiempo . Una construcción para una variante del algoritmo de extensión voraz que utiliza agrupamiento de grafos para aproximar rápidamente las distancias del grafo se ejecuta en tiempo en espacios euclídeos de cualquier dimensión acotada, y puede producir árboles de extensión con propiedades (aproximadamente) idénticas a las de los árboles de extensión voraces. El mismo método puede extenderse a espacios con dimensiones acotadas de dimensión doblante.
Propiedades La misma construcción voraz produce árboles de extensión en espacios métricos arbitrarios, pero en espacios euclídeos posee buenas propiedades, algunas de las cuales no se cumplen de forma más general.
El árbol de extensión geométrico voraz en cualquier espacio métrico siempre contiene el árbol recubridor mínimo de su conjunto de vértices, ya que el algoritmo de construcción voraz sigue el mismo orden de inserción de aristas que el algoritmo de Kruskal para árboles de extensión mínimos. Si el algoritmo del árbol de extensión voraz y el algoritmo de Kruskal se ejecutan en paralelo, considerando los mismos pares de vértices en el mismo orden, cada arista añadida por el algoritmo de Kruskal también será añadida por el algoritmo del árbol de extensión voraz, debido a que los extremos de los árboles de extensión son los mismos. La arista no estará ya conectada por un camino. En el caso límite en que es suficientemente grande (por ejemplo, , donde es el número de vértices en el grafo), ambos algoritmos producen el mismo resultado.
En espacios euclídeos de dimensión acotada, para cualquier constante , los extensores geométricos voraces sobre conjuntos de puntos tienen grados acotados, lo que implica que también tienen aristas. Esta propiedad no se extiende ni siquiera a espacios métricos con buen comportamiento: existen espacios con dimensión doblante acotados donde el extensor voraz tiene grado de vértice no acotado. Sin embargo, en tales espacios el número de aristas sigue siendo .
Los extensores geométricos voraces en espacios euclídeos de dimensión acotada también tienen un peso total como máximo igual a una constante multiplicada por el peso total del árbol de extensión mínima euclídea. Esta propiedad se mantiene en espacios de dimensión duplicante acotada.
Referencias
Categoría:Algoritmos geométricos Categoría:Grafos geométricos