Árbol de diámetro mínimo que abarca

En geometría métrica y geometría computacional , un árbol de expansión de diámetro mínimo de un conjunto finito de puntos en un espacio métrico es un árbol de expansión en el que el diámetro (la longitud del camino más largo en el árbol entre dos de sus puntos) es lo más pequeño posible. ^{[ 1 ]}

Siempre es posible encontrar un árbol de expansión de diámetro mínimo con uno o dos vértices que no sean hojas. Esto se puede demostrar transformando cualquier otro árbol en un árbol de esta forma especial, sin aumentar su diámetro. Para ello, consideremos el camino más largo en cualquier árbol dado (su camino de diámetro) y el vértice o arista en el punto medio de este camino. Si hay un vértice en el punto medio, es el vértice no hoja de una estrella , cuyo diámetro es como máximo igual al del árbol dado. Si el punto medio está dentro de una arista del árbol dado, entonces existe un árbol que incluye esta arista, y en el cual cada vértice restante es una hoja conectada al extremo de esta arista que es más cercano en el árbol dado, con un diámetro como máximo igual al del árbol dado. ^{[ 1 ]}

Debido a esta forma especial, es posible construir un árbol de expansión de diámetro mínimo de${\displaystyle n}$puntos en el tiempo${\displaystyle O(n^{3})}$, suponiendo que la distancia entre dos puntos se puede calcular en tiempo constante. Para ello, se prueban todos los candidatos para el punto único o par de puntos que no sean hojas. Cada punto único se puede probar en${\displaystyle O(n)}$tiempo. Cada par de puntos también se puede probar en${\displaystyle O(n)}$, después de un paso de precomputación en el que, para cada punto, los demás puntos se ordenan según su distancia a él. Para probar un par de puntos, se comienza con un árbol en el que todos los puntos restantes están unidos a un punto del par, y luego, en orden descendente según la distancia a ese punto, se vuelven a unir estos puntos uno a uno al otro punto del par, registrando el diámetro del árbol en cada paso. Hay${\displaystyle O(n^{2})}$pares candidatos de puntos no hoja, cada uno de los cuales puede evaluarse en el tiempo${\displaystyle O(n)}$, dando un límite de tiempo total de${\displaystyle O(n^{3})}$. ^{[ 1 ]}

El problema de construir un árbol de expansión de diámetro mínimo es diferente al de calcular el diámetro de los puntos dados, es decir, la distancia máxima entre pares de puntos. Para algunos conjuntos de puntos, el diámetro de los puntos y el diámetro de su árbol de expansión de diámetro mínimo son iguales; para otros (por ejemplo, tres puntos equidistantes), estas dos distancias pueden diferir entre sí hasta en un factor de dos.

Para el espacio métrico de distancias de camino más corto en un grafo no dirigido ponderado , un árbol de expansión de diámetro mínimo también puede ser un árbol de expansión del grafo, un árbol cuyas aristas pertenecen todas al grafo. Sin embargo, esto puede requerir que tenga más de dos vértices no hoja. En este caso, el problema es equivalente a encontrar un 1-centro absoluto del grafo. Este es un punto en un espacio métrico obtenido del grafo dado reemplazando cada arista por un intervalo continuo de la misma longitud. Es decir, puede ser un vértice o puede estar ubicado a mitad de camino a lo largo de cualquier arista del grafo dado. Entre tales puntos, el 1-centro absoluto es un punto que minimiza la distancia máxima a todos los vértices. El árbol de camino más corto desde este punto a todos los vértices en el grafo es un árbol de expansión de diámetro mínimo del grafo. ^{[ 2 ]} El problema del 1-centro absoluto se introdujo mucho antes del primer estudio del problema del árbol de expansión de diámetro mínimo, ^{[ 2 ] [ 3 ]} y en un grafo con${\displaystyle n}$vértices y${\displaystyle m}$bordes se puede resolver a tiempo${\displaystyle O(mn+n^{2}\log n)}$. ^{[ 2 ] [ 4 ]}

La solución exacta del problema del árbol de expansión de diámetro mínimo, en el plano euclidiano , puede acelerarse desde${\displaystyle O(n^{3})}$a${\displaystyle n^{17/6+o(1)}}$, a costa de utilizar estructuras de datos de búsqueda de rango complicadas . El mismo método se extiende a dimensiones superiores, con reducciones menores en el exponente en comparación con el algoritmo cúbico. En${\displaystyle d}$dimensiones, el límite de tiempo para este método es

${\displaystyle \displaystyle O\left(n^{3-{\tfrac {1}{(d+1)(\lceil d/2\rceil +1)}}+o(1)}\right).}$^{[ 5 ]}

Se conoce un esquema de aproximación en tiempo polinomial para el árbol de expansión de diámetro mínimo en el plano. Para cualquier${\displaystyle \varepsilon >0}$, se puede encontrar un árbol cuyo diámetro es como máximo${\displaystyle 1+\varepsilon }$veces el óptimo, en tiempo${\displaystyle O(n+\varepsilon ^{-3})}$El algoritmo consiste en aproximar la entrada mediante los puntos de una cuadrícula gruesa, elegida para obtener el mejor árbol entre un pequeño número de orientaciones de la cuadrícula. ^{[ 6 ]}

Para puntos en el plano euclidiano, el problema del árbol de expansión de diámetro mínimo también puede aproximarse mediante el árbol de expansión dipolar de suma mínima. Este es un árbol con dos vértices no hoja, que minimiza la suma de dos cantidades: la distancia entre los dos vértices no hoja y la mayor distancia desde un vértice hoja al más cercano de los dos vértices no hoja. Esta aproximación puede hallarse en el tiempo${\displaystyle O(n^{2}\log n)}$y logra una relación de aproximación de${\displaystyle {\tfrac {4}{3}}}$. ^{[ 7 ]}

Para el árbol de diámetro mínimo entre los árboles con un solo vértice que no es una hoja, el vértice que no es una hoja del árbol es el 1-centro de los puntos.

Si se permite añadir puntos de Steiner adicionales al conjunto de puntos dado, su adición puede reducir el diámetro. En este caso, existe un árbol generador de Steiner de diámetro mínimo con un único vértice no hoja, un punto de Steiner en el centro de la esfera delimitadora más pequeña de los puntos. Su diámetro es el doble del radio de esta esfera. Para puntos en un espacio euclidiano de dimensión acotada, esta esfera y este árbol se pueden encontrar en tiempo lineal utilizando algoritmos para el problema del círculo más pequeño y sus generalizaciones. ^{[ 1 ]}