Geometry and Combinatorics

The Euclidean Steiner problem

What is the shortest network that interconnects the three vertices of an equilateral triangle of edge length 1? Any pair of edges of the triangle form a minimal spanning tree of the three points. This tree has total length 2, but it is not the shortest.

Join the three vertices to the centroid of the triangle to obtain a tree of length .

This new point is the so-called Fermat-Torriceli point of the three vertices: the unique point whose sum of distances to the 3 vertices is a minimum. This tree is indeed the shortest tree joining the original 3 vertices, but it has one more vertex. The new vertex  is called a Steiner point, and the tree a Steiner minimal tree: a tree that is shortest among all those whose vertex set includes the original 3 points.

Consider the 4 vertices of a square of edge length 1. A minimal spanning tree has length 3.

As before, the network that joins all 4 vertices to the centre of the square is shorter: .

Indeed, the centre is again the Fermat-Torriceli point of the four given points. However, there is an even shorter tree interconnecting the 4 vertices, one with two Steiner points.

It has length , and is a Steiner minimal tree of the 4 vertices of the square. This example incidentally shows that Steiner minimal trees are in general not unique: rotating by gives another Steiner minimal tree.

In general, given any finite set of terminals in some space, a Steiner tree is any tree whose vertex set is a subset of the space and contains . A Steiner minimal tree (SMT) of is then any shortest Steiner tree of .

The Steiner problem can now be described as the problem of finding a SMT of any given finite set of points in the space. Much has been said about the history of this problem.

In particular we mention that Karl Menger already considered Steiner trees in general metric spaces in 1931, that Gilbert and Pollak (1968 introduced the name Steiner minimal tree, since Courant and Robbins (1941) referred to Steiner in their description of this problem. For a further historical information see Bern and Graham 1988, Hwang, Richards and Winter 1992, Cieslik 1998, and  Korte and Nesetril 2001.

The algorithmic problem of finding a SMT of a given set of points is already NP-hard in the Euclidean plane (Garey, Graham and Johnson 1977), but there are polynomial approximation schemes (Arora 1998), as well as exact algorithms that are feasible at least for up to 2000 points (Warme, Winter and Zachariasen 2000).

In the next installment, I’ll introduce spaces other than the Euclidean plane.

References

• S. Arora (1998), Polynomial time approximation schemes for {E}uclidean traveling salesman and other geometric problems, J. ACM 45, 753–782.
• M.W. Bern and R.L. Graham (1988), The shortest-network problem, Scientific American, January 1988, 84–89.
• Dietmar Cieslik (1998), Steiner minimal trees, Nonconvex Optimization and its
  Applications, vol.~23, Kluwer Academic Publishers, Dordrecht.
• R. Courant and H. Robbins (1941), What is mathematics?, Oxford Univ. Press, Oxford.
• M. R. Garey, R. L. Graham, and D. S. Johnson (1977), The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32, 835–839.
• E. N. Gilbert and H. O. Pollak (1968), Steiner minimal trees, SIAM J. Appl. Math. 16, 1–29.
• F. K. Hwang, D. S. Richards, and P. Winter (1992), The Steiner tree problem, Ann. Discrete Math., vol. 53, North-Holland, Amsterdam.
• Bernhard Korte and Jaroslav Nesetril (2001), Vojtech Jarnik’s work in combinatorial optimization, Discrete Math. 235, 1–17.
• Karl Menger (1931), Some applications of point-set methods, Ann. of Math. (2) 32, 739–760.
• D. M. Warme, P. Winter, and M. Zachariasen (2000), Exact Algorithms for Plane Steiner Tree Problems: A Computational Study. In: Advances in Steiner Trees  (D.-Z. Du, J.~M. Smith, and J.~H. Rubinstein, eds.), Kluwer Academic Publishers, Boston, pp.~81–116.