📐 Steiner tree problem
A Steiner tree connects a set of points with a network of minimal weight. It is similar to the minimum spanning tree, where each edge of the network directly joins vertices from the initial set of points.
A few years ago I made a school project about the Euclidean Steiner tree problem (in French: report and slides). I had written an algorithm which is incredibly slow. Nevertheless, I always wanted to demo it somewhere.
The algorithm
The algorithm will generate trees connecting a set of n points in the Euclidean plane. The generated candidates with minimal total length are Steiner tree.
Kruskal's algorithm for the minimum spanning tree
First, the minimum spanning tree is a Steiner tree candidate. Kruskal's algorithm computes the MST:
For 3 points: compute Fermat point
In a triangle ABC, Fermat point F minimizes the length AF+BF+CF. If all angles of the triangle are less than 120°, then F is the triangle's first isogonic center, else F is the point of the triangle where the angle is greater than 120°. The Steiner tree is formed by the edges connecting the vertices of the triangle to the Fermat point.
For n>3 points: recursivity!
When selecting 2 points A and B, 3 Steiner trees can be formed and combined:
- a Steiner tree connecting to A;
- a Steiner tree connecting to B;
- a Steiner tree connecting to a third point C, constructed from an equilateral triangle having AB for an edge;
Combining the 3 trees and replacing the edge connected to C (CC') with the Steiner tree of ABC' produces a candidate for the Steiner tree of the n points.
One problem in the above solution is that the algorithm must iterate through the 3n tripartitions of the set of points. The search can go a bit faster with the restriction to connected partitions. The following demo shows how the tripartitions are generated.
By combining all solutions mentioned above, we get an algorithm that finds all possible candidate trees.
From 7 points and more, this algorithm gets incredibly slow. Even though the problem is NP-hard, some solutions are very efficient, for example GeoSteiner.
Technical considerations
Because the algorithm is very slow, it is difficult to produce a dynamic interactive representation. Several tools or tricks greatly improved the demos visible in this article.
Generators
The algorithm yields information during its search for the Steiner tree with the help of Generators.
Web workers
Web Workers take over the slow search for candidates, hence keeping the main thread unblocked. This allows users to keep interacting with the application.