June 19, 2020
📐 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;