There is the recent improvement in Expert Layout Editor, the “Shortest path” option was added to Flight line styles (Net Bar). This option allows to build the shortest tree (network) connecting all selected nodes.

Figure 1. Layout Expert Editor screenshot.

“Tree” means the network of vertices (nodes) connected with undirected edges (lines) which has two basic properties:

Any two vertices are connected with some path.
There are no unnecessary edges, in other words if any edge is removed then the first property will be violated.

Figure 2. There are no edges.

“Shortest tree” means the tree with minimal summarized length of edges. It is also called the Minimum Spanning Tree (MST). Minimum Spanning Tree of the given set of points P on Euclidean plane is called Euclidean Minimum Spanning Tree (EMST).

Algorithm

There are a lot of algorithms for finding the Minimum Spanning Tree (one of them is well-known Prim’s algorithm, which is described below), but their common problem is bad productivity.

Most of these algorithms require at least O(n2) time (where n is number of vertices), because the first step for these algorithms is building of the complete graph with all possible edges, where each vertex is directly connected with any other vertex. This operation takes O(n2) time.

Such slow algorithms can be used with small number of vertices but are absolutely inefficient with huge number of vertices. For example, processing of 10,000 vertices will be about 1,000,000 times longer than processing of 10 vertices.

To avoid this problem the set P of points on Euclidean plane is processed in two steps.

The first step is finding the Delaunay triangulation (Figure 3) for n points on Euclidean plane using the “divide and conquer” algorithm (presented in [1]).

Figure 3. Step 1 – creating the Delaunay triangulation
using “divide and conquer” algorithm

During second step we run the Prim’s algorithm on the Delaunay triangulation (Figure 4) to find the Minimum Spanning Tree.

Figure 4. Step 2 – finding the Minimum Spanning
Tree using Prim’s algorithm

The total processing time is O(n^.log(n)), so processing time grows almost linearly with number of processed points.

The results of described two-steps algorithm is EMST because of well-known theorem.

EMST of given set of points P on plane is a subgraph of Delaunay triangulation of P.

Delaunay Triangulation and “Divide and Conquer” Algorithm

The Delaunay triangulation is a triangulation in which every circumcircle of a triangle is an empty circle. Figure 3 shows the example of Delaunay triangulation.

The common idea of the "divide and conquer" algorithm is to process the set of vertices recursively.
The original set of vertices V = {v₁, ..., v_n}, v_i = (x_i, y_i) is sorted by x and y coordinates so that v_i < v_i+1, that means x_i x_i+1, and if x_i = x_i+1 then y_i < y_i+1.
The total set of vertices V is divided into two parts V₁ = {v₁, ..., v_k} and V₂ = {v_k+1, ..., v_n}, V₁V₂ = V according to sort order (left part and right part).

Prim's Algorithm

Prim's algorithm processes graph G = (V, E) of n vertices V = {v₁,..., v_n} and m undirected edges E = {e₁,..., e_m} and removes unnecessary edges.

First step is to choose an arbitrary vertex v₁ V and to build the set of processed vertices P = {v₁}, consisting only of v₁.
Then on every step one new vertex v_i is added to the set of processed vertices P. To choose this vertex we look for smallest edge e = (v_j, v_k) connecting the processed vertices with unprocessed, v_j P, v_k V\P.
Process is repeated until there are no unprocessed vertices more.

Figure 4 shows the results of Prim’s algorithm.

References

Guibas, L. and Stolfi, J., “Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams”, ACM Transactions on Graphics, Vol.4, No.2, April 1985, pages 74-123.
Okabe, A.; Boots, B.; and Sugihara, K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. New York: Wiley, 1992.
Lee, D. T. and Schachter, B. J. “Two Algorithms for Constructing a Delaunay Triangulation.” Int. J. Computer Information Sci. 9, 219-242, 1980.

Download pdf Version