Árbol de expansión mínimo euclidiano

El árbol de expansión mínimo euclidiano ( árbol de expansión mínimo euclidiano , EMST  ) es el árbol de expansión mínimo de un conjunto de n puntos en el plano (o más generalmente, en ), donde el peso de un borde entre cualquier par de puntos es la distancia euclidiana entre dos puntos. En términos simples, EMST vincula un conjunto de puntos con segmentos de línea para que la longitud total de todos los segmentos sea mínima y se pueda llegar a cualquier punto desde otro punto a lo largo de estos segmentos.

En el plano EMST para un conjunto dado de puntos se puede encontrar en el tiempo Θ ( n log n ) usando el espacio O( n ) al calcular un modelo de árbol de decisión algebraico . Los algoritmos probabilísticos más rápidos se conocen con complejidad en modelos de computación más fuertes que modelan con mayor precisión las capacidades de las computadoras reales [1] .

En dimensiones superiores ( ), encontrar el algoritmo óptimo sigue siendo un problema abierto.

Límite inferior

Se puede establecer un límite inferior asintótico Ω ( n log n ) para la complejidad temporal del problema EMST en modelos computacionales restringidos, desde el árbol de decisión algebraico y los modelos de árbol de decisión algebraico, en los que el algoritmo tiene acceso a los puntos de entrada solo a través de Ciertas primitivas restringidas, que realizan cálculos algebraicos simples en coordenadas. En estos modelos , el problema de un par de puntos más cercanos toma tiempo , pero el par más cercano será necesariamente un borde EMST, por lo que EMST también toma esa cantidad de tiempo [2] . Sin embargo, si los puntos de entrada tienen coordenadas enteras y las operaciones bit a bit y la indexación de tablas sobre las coordenadas están disponibles, entonces son posibles algoritmos más rápidos [1] .

Algoritmos para calcular EMST en un avión

El algoritmo más simple para encontrar un EMST en el espacio 2D, dados n puntos, es construir un gráfico completo de n vértices que tenga n ( n -1 )/2 aristas, calcular el peso de cada arista encontrando la distancia entre cada par de puntos, y luego hacer un algoritmo de árbol de expansión mínimo estándar (como una versión del algoritmo de Prim o el algoritmo de Kruskal ) en ese gráfico. Dado que este gráfico tiene Θ ( n 2 ) aristas para n puntos diferentes, construir el gráfico requiere tiempo Ω ( n 2 ). La solución al problema también requiere un espacio de tamaño para almacenar todos los bordes.

Para un enfoque más avanzado para encontrar EMST en el plano, tenga en cuenta que es un subgráfico de cualquier triangulación de Delaunay de n puntos, lo que reduce significativamente el número de aristas:

  1. Construimos una triangulación de Delaunay en tiempo O( n log n ) usando memoria O( n ). Dado que la triangulación de Delaunay es un grafo plano y el número de aristas es como máximo tres veces el número de vértices, en cualquier grafo plano, esta construcción genera solo O( n ) aristas.
  2. Etiquetamos cada borde con su longitud.
  3. Ejecutamos el algoritmo para encontrar el árbol de expansión mínimo en este gráfico. Dado que hay O( n ) aristas, este algoritmo tardará O( n log n ) si se utiliza alguno de los algoritmos de árbol de expansión mínimo estándar, como el algoritmo de Boruvka , el algoritmo de Prim o el algoritmo de Kruskal .

En última instancia, el algoritmo requiere O( n log n ) tiempo y O( n ) espacio .

Si las coordenadas de entrada son números enteros y se pueden usar como una matriz de índices , son posibles algoritmos más rápidos: la triangulación de Delaunay se puede construir usando un algoritmo probabilístico en el tiempo con expectativa matemática [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 usando una variante del algoritmo de Boruvka que elimina todos los bordes menos los más baratos entre cada par de componentes después de cada paso del algoritmo [3] [4] . Por lo tanto, el tiempo de ejecución total esperado de este algoritmo es [1] .

Dimensiones superiores

El problema se puede generalizar a n puntos del espacio d -dimensional ℝ d . En dimensiones superiores, la conexión definida por la triangulación de Delaunay (que divide el casco convexo en simples d -dimensionales ) contiene un árbol de expansión mínimo. Sin embargo, la triangulación puede contener un gráfico completo [5] . Por esta razón, tomará tiempo encontrar un árbol de expansión mínimo euclidiano como árbol de expansión de un gráfico completo o como árbol de expansión de las triangulaciones de Delaunay . En el espacio tridimensional, puede encontrar el árbol de expansión mínimo en el tiempo , y en cualquier espacio de mayor dimensión, puede resolver el problema 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 [5] . Para puntos aleatorios uniformemente distribuidos, los árboles de expansión mínimos se pueden calcular a la misma velocidad que la clasificación [6] . Utilizando una descomposición bien separada de pares , se puede obtener una aproximación en el tiempo [7] .

Subárboles de la triangulación de Delaunay

Todos los bordes de la EMST son bordes del gráfico de vecindad relativa [8] [9] [10] , que a su vez son bordes del gráfico de Gabriel , que son bordes en la triangulación de puntos de Delaunay [11] [12] , que puede demostrarse mediante un equivalente a la afirmación contrapositiva : cualquier arista no incluida en la triangulación de Delaunay no está contenida en ninguna EMST. La demostración se basa en dos propiedades de los árboles de expansión mínimos y la triangulación de Delaunay:

  1. ( propiedad de los ciclos del árbol de expansión mínimo): Para cualquier ciclo C en un gráfico, si el peso de un borde e del gráfico C es mayor que el peso de otro borde C, ese borde no puede pertenecer a un árbol de expansión mínimo .
  2. (propiedad de las triangulaciones de Delaunay): si hay un ciclo con dos puntos de entrada en su límite que no contiene otros puntos de entrada, el segmento entre estos dos puntos es un borde de cualquier triangulación de Delaunay.

Considere un borde e entre dos puntos de entrada p y q que no es un borde de triangulación de Delaunay. La propiedad 2 implica que un ciclo C con e como diámetro debe contener algún otro punto r en su interior. Pero entonces r está más cerca tanto de p como de q que entre sí, y por lo tanto la arista de p a q es la más larga en el ciclo de puntos y, por propiedad 1 e , no pertenece a ninguna EMST.

Tamaño esperado

El tamaño esperado de la EMST para grandes conjuntos de puntos fue determinado por J. Michael Steel [13] . Si es la función de densidad de la función de probabilidad para la selección de puntos, entonces para grande y el tamaño de la EMST es aproximadamente igual a

donde es una constante que depende únicamente de la dimensión de . No se conoce el valor exacto de las constantes, pero podemos estimarlo a partir de la experiencia 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 el precio depende solo de la unidad de longitud del producto de conexión. Sin embargo, dado que esto proporciona un límite inferior absoluto en la cantidad de producto requerido, la mayoría de estas redes prefieren un gráfico con conexión de borde k en lugar de un árbol, de modo que la pérdida de una sola conexión no rompa la red.

Otra aplicación de EMST es un algoritmo de aproximación de factores constantes para la solución aproximada del problema del viajante de comercio euclidiano , una versión del problema del viajante de comercio sobre un conjunto de puntos en un plano con aristas cuyos precios son iguales a sus longitudes. Esta versión realista del problema se puede resolver aproximadamente con un factor de 2 calculando la EMST, siguiendo su límite, que delinea todo el árbol, y luego eliminando todos los vértices que ocurren varias veces (dejando solo uno).

Implementación planar

El problema de implementación de los árboles de expansión mínima euclidiana se plantea de la siguiente manera: dado un árbol , encuentre la posición D ( u ) de cada vértice tal que T sea un árbol de expansión mínima , o determine que tales posiciones no existen. Verificar la existencia de una realización en el plano es un problema NP-completo [14] .

Notas

  1. ↑ 1 2 3 4 Buchin y Mulzer, 2009 , pág. 139–148.
  2. ↑ Yao, 1989 , pág. 308–313.
  3. ↑ Eppstein, 1999 , pág. 425–461.
  4. ↑ Yeguas, 2004 , pág. 315–320.
  5. ↑ 1 2 Agarwal, Edelsbrunner, Schwarzkopf, Welzl, 1991 , p. 407–422.
  6. ↑ Chatterjee, Connor, Kumar, 2010 , pág. 486–500.
  7. ↑ Smid, 2005 .
  8. ↑ Jaromczyk, Toussaint, 1992 , pág. 1502-1517
  9. ↑ Toussaint, 1981 , pág. 860–861.
  10. ↑ Toussaint, 1980 , pág. 261–268.
  11. ↑ Pless, 2003 .
  12. ↑ Sedgewick, Wayne, 2007 .
  13. ↑ Steele, 1988 , pág. 1767-1787
  14. ↑ Eades, Whitesides, 1994 , pág. 49–56.

Literatura