Un árbol de extensión mínima euclídea (o también árbol de longitud mínima euclídea) de un conjunto finito de puntos en el plano o en un espacio euclídeo de dimensiones superiores, conecta todos los puntos dados mediante un sistema de segmentos con los puntos como extremos, minimizando la longitud total de los segmentos. En él, dos puntos cualesquiera siempre quedan conectados entre sí mediante un camino que pasa por los segmentos de línea del árbol. Se puede encontrar como el árbol recubridor mínimo de un grafo completo con los puntos como vértices y la distancia euclídea entre puntos como pesos de las aristas.

Las aristas del árbol de extensión mínima se encuentran en ángulos de al menos 60°, como máximo seis por vértice. En dimensiones superiores, el número de aristas por vértice está limitado por el número de osculación de 1-esferas tangentes. La longitud total de las aristas, para puntos en situados en un cuadrado unidad, es como máximo proporcional a la raíz cuadrada del número de puntos. Cada arista se encuentra en una región vacía del plano, y estas regiones se pueden usar para demostrar que el árbol de extensión mínima euclídea es un subgrafo de otros grafos, incluidos el grafo de vecindad relativa y la triangulación de Delaunay. Al construir la triangulación de Delaunay y luego aplicar un algoritmo de árbol de extensión mínimo del grafo, el árbol de extensión mínimo de puntos dados en un plano se puede encontrar en el tiempo , como se expresa en la notación O grande. Este límite es el óptimo en algunos modelos de cálculo, aunque existen algoritmos probabilisticos más rápidos para puntos con coordenadas enteras. Para puntos en dimensiones superiores, encontrar un algoritmo óptimo sigue siendo un problema no resuelto.

Definición y problemas relacionados Un árbol de extensión mínima euclídea, para un conjunto de puntos en un plano o en un espacio euclídeo de dimensión superior, es un sistema de segmentos que tiene solo los puntos dados como puntos finales, cuya unión incluye todos los puntos en un conjunto conexo, y que tiene la longitud total mínima posible de cualquier sistema de este tipo. Una red de este tipo no puede contener un anillo de segmentos poligonal, dado que si existiera, la red podría acortarse eliminando un lado del polígono. Por lo tanto, la red de longitud mínima forma un árbol. Esta observación conduce a la definición equivalente de que un árbol de extensión mínima euclídea es un árbol de segmentos rectilíneos entre pares de puntos dados, de longitud total mínima. El mismo árbol también puede describirse como el árbol recubridor mínimo de un grafo completo ponderado, que tiene los puntos dados como sus vértices y las distancias entre puntos como pesos de las aristas. Los mismos puntos pueden tener más de un árbol de extensión mínimo. Por ejemplo, para los vértices de un polígono regular, eliminar cualquier borde del polígono produce un árbol de extensión mínimo.

Las publicaciones sobre el árbol de extensión mínima euclídea comúnmente lo abrevian como "EMST". También pueden denominarse "árboles de extensión geométrica mínima", pero ese término puede usarse de manera más general para espacios geométricos con distancias no euclídeas, como espacios . Cuando el contexto de los conjuntos de puntos euclídeos es claro, se les puede llamar simplemente "árboles de extensión mínima".

Varias otras redes geométricas estándar están estrechamente relacionadas con el árbol de extensión mínima euclídea: El problema del árbol de Steiner busca un sistema de segmentos rectilíneos que conecten todos los puntos dados, pero sin requerir que los segmentos comiencen y terminen solo en los puntos dados. En este problema, se pueden agregar puntos adicionales como puntos finales de los segmentos, lo que permite que el árbol de Steiner sea más corto que el árbol de extensión mínimo. En el problema del viajante euclídeo, los segmentos de línea de conexión deben comenzar y terminar en los puntos dados, como en el árbol de extensión mínima. Además, cada punto puede tocar como máximo dos segmentos de línea, por lo que el resultado forma una cadena poligonal. Debido a esta restricción, el camino óptimo puede ser más largo que el árbol de extensión mínima euclídea, pero como máximo es el doble. Los árboles de extensores geométricos son redes de bajo peso que, al igual que el árbol de extensión mínima, conectan todos los puntos. A diferencia del árbol de extensión mínima, todos estos caminos de conexión deben ser cortos y tener una longitud proporcional a la distancia entre los puntos que conectan. Para lograr esta propiedad, estas redes generalmente tienen ciclos y, por lo tanto, no son árboles.

Propiedades Ángulos y grados de vértice

Siempre que dos aristas de un árbol de extensión mínima euclídea se encuentran en un vértice, deben formar un ángulo de 60° o más, dándose la igualdad solo cuando forman dos lados de un triángulo equilátero. Esto se debe a que, para dos aristas que forman un ángulo más agudo, una de las dos aristas podría ser reemplazada por la tercera arista, más corta, del triángulo que forman, formando un árbol con una longitud total menor. En comparación, el problema del árbol de Steiner tiene un límite de ángulo más fuerte: un árbol de Steiner óptimo tiene todos los ángulos de al menos 120°.

El mismo límite de ángulo de 60° también ocurre en el problema del número de osculación, de encontrar el número máximo de 1-esferas en el espacio euclídeo que pueden ser tangentes a una esfera unitaria central sin que dos esferas se crucen (más allá de un punto de tangencia). Los puntos centrales de estas esferas tienen un árbol de extensión mínimo en forma de estrella, con el punto central conectado con todos los demás puntos. Por el contrario, para cualquier vértice de cualquier árbol de extensión mínimo, se pueden construir esferas unitarias no superpuestas centradas en y en puntos dos unidades en cada uno de sus aristas, con una tangencia para cada vecino de . Por lo tanto, en el espacio dimensional, el máximo grado posible de un vértice (el número de aristas del árbol de extensión conectados a él) es igual al número de esferas osculadoras en dimensiones. Los árboles de extensión mínimos planos tienen como máximo seis grados, y cuando un árbol tiene grado seis siempre hay otro árbol de extensión mínimo con un grado máximo de cinco. Los árboles de extensión mínima tridimensionales tienen un grado máximo de doce. Las únicas dimensiones superiores en las que se conoce el valor exacto del número de osculaciones son las dimensiones cuatro, ocho y 24.

Para puntos generados aleatoriamente a partir de una distribución continua determinada, el árbol de extensión mínimo es casi seguramente único. El número de vértices de cualquier grado dado converge, para un gran número de vértices, a una constante multiplicada por ese número de vértices. Los valores de estas constantes dependen del grado y la distribución. Sin embargo, incluso para casos simples (como el número de hojas de puntos uniformemente distribuidos en un cuadrado unitario), no se conocen sus valores precisos.

Regiones vacías

Para cualquier arista de cualquier árbol de extensión mínima euclídea, la lúnula (o vesica piscis, vientre de pez) formada al intersecar las dos circunferencias de radio , ya que en su interior no pueden tener ningún otro vértice dado . Dicho de otra manera, si algún árbol tiene una arista cuya lúnula contiene un tercer punto , entonces no tiene una longitud mínima. Porque, según la geometría de las dos circunferencias, estaría más cerca de y de que estos dos puntos entre sí. Si la arista se eliminara del árbol, permanecería conectado a uno de los puntos o , pero no al otro. Reemplazar la arista eliminada por o por (cualquiera de estas dos aristas vuelva a conectar al vértice del cual se desconectó) produciría un árbol más corto.

Para cualquier arista de cualquier árbol de extensión mínima euclídea, el rombo con ángulos de 60° y 120°, que tiene como su diagonal más larga, está separado de los rombos formados de manera análoga por todas las demás aristas. Dos aristas que comparten un punto final no pueden tener rombos superpuestos, porque eso implicaría un ángulo de arista superior a 60°, y dos aristas disjuntas no pueden tener rombos superpuestos. Si los tuvieran, la arista más larga de las dos podría ser reemplazada por una arista más corta entre los mismos cuatro vértices.

Supergrafos Ciertos grafos tienen definiciones que involucran regiones vacías en conjuntos de puntos, de lo cual se deduce que contienen todas las aristas que pueden ser parte de un árbol de extensión mínima euclídea. Estos incluyen: El grafo de vecindad relativa, que tiene una arista entre cualquier par de puntos siempre que la lúnula que definen esté vacía. El grafo de Gabriel, que tiene una arista entre cualquier par de puntos siempre que el círculo que tiene el par de puntos como diámetro esté vacío. La triangulación de Delaunay, que tiene una arista entre cualquier par de puntos siempre que exista un círculo vacío que tenga el par de puntos como cuerda. El grafo de Urquhart, formado a partir de la triangulación de Delaunay eliminando la arista más larga de cada triángulo. Para cada arista restante, los vértices de los triángulos de Delaunay que usan esa arista no pueden estar dentro de la lúnula vacía del grafo de vecindad relativa.

Debido a que los criterios de región vacía para estos grafod son progresivamente más débiles, estos grafos forman una secuencia ordenada de subgrafos. Es decir, usando el símbolo "⊆" para denotar la relación de subconjunto entre sus aristas, estos grafos tienen las relaciones:

Árbol de extensión mínima euclídea ⊆ grafo de vecindad relativa ⊆ grafo de Urquhart ⊆ grafo de Gabriel ⊆ triangulación de Delaunay.

Otro grafo que garantiza contener el árbol de extensión mínimo es el grafo de Yao, determinado para puntos en el plano dividiendo el plano alrededor de cada punto en seis cuñas de 60° y conectando cada punto con el vecino más cercano en cada cuña. El grafo resultante contiene el grafo de vecindad relativa, porque dos vértices con una lúnula vacía deben ser vecinos más cercanos entre sí en sus cuñas. Como ocurre con muchos de los otros grafos geométricos anteriores, esta definición se puede generalizar a dimensiones superiores y (a diferencia de la triangulación de Delaunay) sus generalizaciones siempre incluyen un número lineal de aristas.

Longitud total Para puntos en un cuadrado unidad (o cualquier otra forma fija), la longitud total de las aristas del árbol de extensión mínima es . Algunos conjuntos de puntos, como los puntos espaciados uniformemente en una cuadrícula, alcanzan este límite. Para puntos en un hipercubo unitario en un espacio -dimensional, el límite correspondiente es . El mismo límite se aplica a la longitud total esperada del árbol de extensión mínima para puntos elegidos de forma uniforme e independiente de un cuadrado unitario o de un hipercubo unitario. Volviendo al cuadrado unitario, la suma de los cuadrados de las longitudes de las aristas del árbol de extensión mínima es . Este límite se deduce de la observación de que las aristas tienen rombos disjuntos, con un área proporcional al cuadrado de las longitudes de las aristas. La cota para la longitud total se obtiene aplicando la desigualdad de Cauchy-Bunyakovsky-Schwarz.