Details

Before reading further, I would recommend that you experiment. Choose the position of the regular points, then add some Steiner points and drag them to try to minimize the total length. See if choosing more Steiner points is helpful or not. You will soon recognize that more is not always better, and that an optimal network has very interesting geometric properties. An optimal network is not necessarily unique.

For regular points, an optimal solution depends on the points' relative positions. If they form a triangle with an angle larger than 120°, then the two shortest sides form the optimal network and no Steiner points are needed. On the other hand, if all the angles of the triangle are less than 120°, then an appropriately chosen Steiner point connected to all vertices gives the optimal network. This point is called the Torricelli point (or Fermat point) of the triangle. One way to construct this point is to draw external equilateral triangles on the sides of the triangle and to connect the third vertices of these triangles to the opposite vertices of the original triangle.

For regular points, an optimal solution again depends on their relative positions. If they spread out "nicely," a simple geometric construction involving equilateral triangles drawn on opposite sides of the quadrilateral leads to a solution. On the other hand, there are several arrangements of the original points where this construction does not give an optimal network.

For there are even more possibilities. In some cases, a clever use of circles and equilateral triangles leads to an optimal network.

In general, the Steiner tree problem using Euclidean distances is NP-complete. Finding an optimal solution or even a close-to-optimal solution is difficult. However, an optimal network always exists; it is a tree structure with finitely many Steiner points added, where all angles formed by adjacent edges are not less than 120°, and where at Steiner points exactly three edges meet.

This Demonstration intends to show how these facts help in finding an optimal case for a small number of points. It also highlights a consequence of these properties, namely, that although adding some Steiner points can be helpful, not too many are needed. For example, for , one Steiner point may not be enough, but three are certainly not needed. Try it! By trying to locate Steiner points so that in the network all angles at those points are 120°, you will better understand the concept of angles subtended by the same arc. If you find a solution that looks optimal, you can try to figure out a way to construct it with ruler and compass. For the case of and , the Related Links below show a possible solution.

In the Demonstration, the minimal spanning tree is found using Prim's algorithm; the code is a slight modification of the code used by Frederick Wu in his Demonstration about greedy algorithms for a minimal spanning tree (see the Related Links).

Reference

[1] "Steiner Tree Problem." Encyclopedia of Mathematics. www.encyclopediaofmath.org/index.php/Steiner_tree_problem.