El árbol de expansión mínimo euclidiano o EMST es un árbol de expansión mínimo de un conjunto de n puntos en el plano (o más generalmente en ℝ d ), donde el peso del borde entre cada par de puntos es la distancia euclidiana entre esos dos puntos. En términos más simples, un EMST conecta un conjunto de puntos usando líneas de modo que la longitud total de todas las líneas se minimiza y se puede llegar a cualquier punto desde cualquier otro siguiendo las líneas.
En el plano, un EMST para un conjunto dado de puntos se puede encontrar en Θ ( n log n ) tiempo usando O ( n ) espacio en el modelo de cálculo de árbol de decisión algebraico . Los algoritmos aleatorios más rápidos de complejidad O ( n log log n ) se conocen en modelos de cálculo más potentes que modelan con mayor precisión las capacidades de las computadoras reales. [1]
En dimensiones superiores ( d ≥ 3), encontrar un algoritmo óptimo sigue siendo un problema abierto .
Límite inferior
Se puede establecer un límite inferior asintótico de Ω ( n log n ) para la complejidad temporal del problema EMST en modelos de cálculo restringidos, como el árbol de decisión algebraico y los modelos de árbol de cálculo algebraico , en los que el algoritmo solo tiene acceso a los puntos de entrada a través de ciertas primitivas restringidas que realizan cálculos algebraicos simples en sus coordenadas: en estos modelos, el problema del par de puntos más cercano requiere un tiempo Ω ( n log n ), pero el par más cercano es necesariamente un borde del EMST, por lo que el EMST también requiere esto mucho tiempo. [2] Sin embargo, si los puntos de entrada tienen coordenadas enteras y las operaciones bit a bit y las operaciones de indexación de tablas están permitidas usando esas coordenadas, entonces son posibles algoritmos más rápidos. [1]
Algoritmos para calcular EMST en dos dimensiones
El algoritmo más simple para encontrar un EMST en dos dimensiones, dados n puntos, es construir el gráfico completo en n vértices, que tiene n ( n -1) / 2 aristas, calcular cada peso de arista encontrando la distancia entre cada par de puntos, y luego ejecute un algoritmo de árbol de expansión mínimo estándar (como la versión del algoritmo de Prim o el algoritmo de Kruskal ) en él. Dado que esta gráfica tiene Θ ( n 2 ) aristas para n puntos distintos, construirla ya requiere Ω ( n 2 ) tiempo. Esta solución también requiere un espacio Ω ( n 2 ) para almacenar todos los bordes.
Un mejor enfoque para encontrar el EMST en un plano es notar que es un subgrafo de cada triangulación de Delaunay de los n puntos, un conjunto de aristas muy reducido:
- Calcule la triangulación de Delaunay en el tiempo O ( n log n ) y el espacio O ( n ). Debido a que la triangulación de Delaunay es un gráfico plano , y no hay más de tres veces más aristas que vértices en cualquier gráfico plano, esto genera solo O ( n ) aristas.
- Etiqueta cada borde con su longitud.
- Ejecute un algoritmo de árbol de expansión mínimo de gráfico en este gráfico para encontrar un árbol de expansión mínimo. Puesto que hay O ( n ) los bordes, esto requiere O ( n log n ) tiempo utilizando cualquiera de los mínimos estándar que abarca algoritmos de árboles tales como el algoritmo de Borůvka , el algoritmo de Prim , o el algoritmo de Kruskal .
El resultado final es un algoritmo que toma O ( n log n ) tiempo y O ( n ) espacio.
Si las coordenadas de entrada son números enteros y se pueden usar como índices de matriz , son posibles algoritmos más rápidos: la triangulación de Delaunay se puede construir mediante un algoritmo aleatorio en el tiempo esperado O ( n log log n ). [1] Además, dado que la triangulación de Delaunay es un gráfico plano , su árbol de expansión mínimo se puede encontrar en tiempo lineal mediante una variante del algoritmo de Borůvka que elimina todo menos el borde más barato entre cada par de componentes después de cada etapa del algoritmo. [3] Por lo tanto, el tiempo total esperado para este algoritmo es O ( n log log n ). [1]
Mayores dimensiones
El problema también se puede generalizar a n puntos en el espacio d -dimensional ℝ d . En dimensiones superiores, la conectividad determinada por la triangulación de Delaunay (que, igualmente, divide el casco convexo en simplices d- dimensionales ) contiene el árbol de expansión mínimo; sin embargo, la triangulación puede contener el gráfico completo. [4] Por lo tanto, encontrar el árbol de expansión mínimo euclidiano como un árbol de expansión del gráfico completo o como un árbol de expansión de la triangulación de Delaunay toman O ( dn 2 ) tiempo. Para tres dimensiones es posible encontrar el árbol de expansión mínimo en el tiempo O (( n log n ) 4/3 ), y en cualquier dimensión mayor de tres es posible resolverlo en un tiempo que es más rápido que el límite de tiempo cuadrático para el gráfico completo y los algoritmos de triangulación de Delaunay. [4] Para conjuntos de puntos uniformemente aleatorios, es posible calcular árboles de expansión mínimos tan rápido como ordenar. [5] Usando una descomposición de pares bien separados , es posible producir una aproximación (1 + ε) en el tiempo O ( n log n ). [6]
Subárbol de triangulación de Delaunay
Todos los bordes de un EMST son bordes de un gráfico de vecindad relativa , [7] [8] [9] que a su vez son bordes de un gráfico de Gabriel , que son bordes en una triangulación de Delaunay de los puntos, [10] [11] como se puede probar a través de la declaración contrapositiva equivalente : cada borde que no está en una triangulación de Delaunay tampoco está en ningún EMST. La prueba se basa en dos propiedades de los árboles de expansión mínimos y las triangulaciones de Delaunay:
- (la propiedad del ciclo de los árboles de expansión mínimos): Para cualquier ciclo C en el gráfico, si el peso de una arista e de C es mayor que los pesos de otras aristas de C, entonces esta arista no puede pertenecer a un MST .
- (una propiedad de las triangulaciones de Delaunay): si hay un círculo con dos de los puntos de entrada en su límite que no contiene otros puntos de entrada, la línea entre esos dos puntos es un borde de cada triangulación de Delaunay.
Considere un borde e entre dos puntos de entrada de p y q , que no es un borde de una triangulación de Delaunay. La propiedad 2 implica que el círculo C con e como diámetro debe contener algún otro punto r en su interior. Pero entonces r es cercano a ambos p y q de lo que son el uno al otro, por lo que el borde de P a Q es el borde más largo en el ciclo de los puntos p → q → r → p , y por bienes 1 correo no está en cualquier EMST.
Tamaño esperado
J. Michael Steele determinó el tamaño esperado del EMST para un gran número de puntos . [12] Si es la densidad de la función de probabilidad para seleccionar puntos, luego para grandes y el tamaño del EMST es aproximadamente
dónde es una constante que depende solo de la dimensión . Se desconoce el valor exacto de las constantes, pero se puede estimar a partir de evidencia empírica.
Aplicaciones
Una aplicación obvia de los árboles de expansión mínimos euclidianos es encontrar la red más barata de cables o tuberías para conectar un conjunto de lugares, asumiendo que los enlaces cuestan una cantidad fija por unidad de longitud. Sin embargo, mientras que estos dan un absoluto límite inferior de la cantidad de conexión necesario, la mayoría de tales redes prefieren una k comunicado con los gráfico a un árbol, por lo que el fallo de un link individuo no dividir la red en partes.
Otra aplicación de los EMST es un algoritmo de aproximación de factores constantes para resolver aproximadamente el problema del viajante de comercio euclidiano , la versión del problema del viajante de comercio en un conjunto de puntos en el plano con bordes marcados por su longitud. Esta variación realista del problema se puede resolver con un factor de 2 calculando el EMST, haciendo una caminata a lo largo de su límite que delimita todo el árbol y luego eliminando todas las ocurrencias de cada vértice menos una de esta caminata.
Realización plana
El problema de realización para árboles de expansión mínimos euclidianos se establece de la siguiente manera: Dado un árbol T = ( V , E ), encuentre una ubicación D ( u ) para cada vértice u ∈ V de modo que T sea un árbol de expansión mínimo de D ( u ) : u ∈ V, o determine que no existen tales ubicaciones. La prueba de la existencia de una realización en el avión es NP-difícil . [13]
Ver también
- Árbol de expansión mínimo rectilíneo
Referencias
- ^ a b c d Buchin, Kevin; Mulzer, Wolfgang (2009). Triangulaciones de Delaunay en tiempo O (sort ( n )) y más (PDF) . Proc. 50º Simposio IEEE sobre fundamentos de la informática . págs. 139-148. doi : 10.1109 / FOCS.2009.53 ..
- ^ Yao, AC-C. (1989), "Límites inferiores para árboles de cálculo algebraico con entradas enteras", Proc. 30º Simposio anual sobre los fundamentos de la informática (FOCS 1989) , págs. 308–313, doi : 10.1109 / SFCS.1989.63495.
- ^ Eppstein, David (1999), "Spanning trees and spanners", en Sack, J.-R. ; Urrutia, J. (eds.), Manual de geometría computacional , Elsevier, págs. 425–461; Mareš, Martin (2004), "Dos algoritmos de tiempo lineal para MST en clases de gráficos cerrados menores" (PDF) , Archivum Mathematicum , 40 (3): 315–320.
- ^ a b Agarwal, PK ; Edelsbrunner, H .; Schwarzkopf, O .; Welzl, E. (1991), "Árboles de expansión mínimos euclidianos y pares más cercanos bicromáticos", Geometría discreta y computacional , Springer, 6 (1): 407–422, doi : 10.1007 / BF02574698.
- ^ Chatterjee, S .; Connor, M .; Kumar, P. (2010), "Árboles de expansión mínima geométrica con GeoFilterKruskal", en Festa, Paola (ed.), Symposium on Experimental Algorithms , Lecture Notes in Computer Science, 6049 , Springer-Verlag, págs. 486–500, doi : 10.1007 / 978-3-642-13193-6_41.
- ^ Smid, Michiel (16 de agosto de 2005). "La descomposición de pares bien separados y sus aplicaciones" (PDF) . Consultado el 26 de marzo de 2014 .
- ^ Jerzy W. Jaromczyk y Godfried T. Toussaint, "Gráficos de vecindad relativa y sus parientes", Actas del IEEE , vol. 80, núm. 9, septiembre de 1992, págs. 1502-1517.
- ^ Godfried T. Toussaint, "Comentario sobre algoritmos para calcular el gráfico de vecindad relativa", Electronics Letters , vol. 16, núm. 22, octubre de 1981, págs. 860–861.
- ^ Godfried T. Toussaint, "El gráfico de vecindad relativa de un conjunto plano finito", Reconocimiento de patrones , vol. 12, 1980, págs. 261-268.
- ^ Robert Pless. Clase 17: Diagramas de Voronoi y triangulaciones de Delauney. Primavera de 2003, página de la clase de geometría computacional. Profesor Asociado de Ingeniería y Ciencias de la Computación en la Universidad de Washington. http://www.cs.wustl.edu/~pless/506/l17.html Archivado el 12 de septiembre de 2006 en Wayback Machine.
- ^ Robert Sedgewick y Kevin Wayne. Notas de clase mínimas de Spanning Tree. Ciencias de la Computación 226: Algoritmos y estructuras de datos, primavera de 2007. Universidad de Princeton. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf
- ^ Steele, J. Michael (1988). "Tasas de crecimiento de árboles de expansión mínima euclidiana con bordes ponderados por potencia" (PDF) . Los anales de la probabilidad . 16 (4): 1767-1787. doi : 10.1214 / aop / 1176991596 .
- ^ Eades, Peter ; Whitesides, Sue (1994), "El problema de realización de los árboles de expansión mínima euclidiana es NP-hard", Proc. Décimo Simposio de ACM sobre geometría computacional , págs. 49–56, doi : 10.1145 / 177424.177507.
- Smith College: The Open Problems Project: Problema 5: Árbol de expansión mínimo euclidiano
- Max-Planck-Institut fuer Informatik: Soluciones de ejercicio , por Kavitha Telikepalli (posdata)
- STANN (Michael Connor, Piyush Kumar y Samidh Chatterjee): una biblioteca de C ++ que puede calcular árboles de expansión mínimos euclidianos en dimensiones reducidas