árbol de expansión mínima rectilíneo

En el caso planar, existen algoritmos más eficientes. Estos se basan en la idea de que las conexiones solo pueden ocurrir con el vecino más cercano de un punto en cada octante, es decir, con cada una de las ocho regiones del plano delimitadas por el eje de coordenadas desde este punto y sus bisectrices.

El grafo resultante tiene solo un número lineal de aristas y puede construirse en O( n log n ) utilizando un algoritmo de divide y vencerás ^{[ 1 ]} o un algoritmo de línea de barrido . ^{[ 2 ]}

El problema surge comúnmente en el diseño físico de circuitos electrónicos . En los circuitos integrados modernos de alta densidad, el enrutamiento de cables se realiza mediante cables que consisten en segmentos que discurren horizontalmente en una capa de metal y verticalmente en otra. Como resultado, la longitud del cable entre dos puntos se mide naturalmente con la distancia rectilínea. Si bien el enrutamiento de una red completa con múltiples nodos se representa mejor mediante el árbol de Steiner rectilíneo , el RMST proporciona una aproximación razonable y una estimación de la longitud del cable. ^{[ 3 ]}