ThatsMaths

Steiner’s minimal tree problem is this: Find the shortest possible network interconnecting a set of points in the Euclidean plane. If the points are linked directly to each other by straight line segments, we obtain the minimal spanning tree. But Steiner’s problem allows for additional points – now called Steiner points – to be added to the network, yielding Steiner’s minimal tree. This generally results in a reduction of the overall length of the network.

Jakob Steiner (1796-1863) a Swiss mathematician, was one of the greatest geometers of all time. Born near Berne, he moved to Germany in 1818, and spent most of his life in Berlin, where he was on friendly terms with Jacobi and Abel. The problem we now call Steiner’s problem was originally posed in purely geometric terms, but its solution involves mathematical techniques from combinatorics, analysis and computational science.

The problem is relevant for applications in many areas, including communications, power grids, transport networks, electric circuit layout, facility location, pipeline networks and the efficient design of microchips.

Origins of the Problem

Although the problem was analysed by Jakob Steiner, he was not the first person to consider it. A comprehensive history of the Euclidean Steiner tree problem was published recently by Brazil et al. (2014). They point out that the first person to pose and analyse the problem was the French mathematician Joseph Diaz Gergonne (1771-1859).

Gergonne first considered the Fermat-Torricelli problem, one of the simplest network minimisation problems. This asks for the shortest network connecting three points in the plane. Put another way, given three points in a plane, find a fourth such that the sum of its distances from the first three is as small as possible. This problem was originally posed by Pierre de Fermat in 1643 in a letter to the Italian physicist and mathematician Evangelista Torricelli.

Torricelli found that, if no angle of the triangle linking the three points is greater than 120°, the solution is a point such that the three lines from this point to the vertices meet at angles of 120°. He constructed equilateral triangles on two sides of the triangle, and joined the additional vertex of each to the opposite vertex of the original triangle. These lines cross at a point that provides the solution, as shown here:

If an angle of the triangle equals or exceeds 120°, then the two sides adjacent to this angle provide the minimal network; there is no need for an additional (Steiner) point.

In addition to the Fermat-Torricelli problem, Gergonne analysed a number of generalisations. One of these was the Steiner problem. He expressed it thus: A number of cities are situated at known locations in the plane; the problem is to link them together by a system of canals whose total length is as small as possible. This is the first known statement of the Steiner tree problem.

Gergonne later posed the problem in more abstract terms: Connect any number of given points by a system of lines whose total length is as small as possible. He showed that if there are n given points, no more than n – 2 Steiner points are needed to achieve a minimum. These points are of degree three: three line segments meet at each Steiner point at angles of 120°.

Carl Friedrich Gauss looked at the Steiner problem in 1836. In a letter to the Danish-German astronomer Christian Schumacher that year, he wrote: “I have on occasion considered the railway connection between Harburg [near Hamburg], Bremen, Hannover and Braunschweig.” At that time, no such railways existed, so he was anticipating the theoretical challenge of constructing optimal networks.

What Gauss was discussing was the Steiner problem for four points. In the letter to Schumacher, he drew solutions or several particular cases (Brazil, et al. 2014), but he never returned to the problem.

Solutions for 4 Points in a Rectangle

The book “What is Mathematics?” by Richard Courant and Herbert Robbins, which first appeared in 1941, was very influential. Written in an expository way and accessible to a wide audience, it continued to be popular and is still in print. In Chapter VII, “Maxima and Minima”, Courant and Robbins discuss the Steiner problem at length. Amongst other things, they point out that the solution is not necessarily unique. For example, if four points are given at the corners of a square, there are two solutions, as shown here:

For a unit square, each of these networks is of length 1+√3. It is interesting that neither solution has the same degree of symmetry as the square: the solutions have less symmetry than the problem itself !

Courant and Robbins also discussed an ‘analogue method’ of solving the Steiner problem: an empirical solution can be found using soap films. If two sheets of glass joined by perpendicular struts are dipped in a soap solution, a film forms comprised of plane sections meeting at angles of 120°. Soap films provide a local minimum configuration, but not always the global minimum.

Let us start with the solution for a rectangle with large breadth and small height (panel 1 in the figure below). Imagine a soap film in the form of the minimum Steiner tree. Now we distort the rectangle, increasing the height but keeping the length of the perimeter constant. The topological form of the solution (with a horizontal strut) remains unchanged as it passes through a square shape (panel 3). At some stage (panel 4) the Steiner points coalesce and the solution forms the two diagonals. This is an unstable configuration and immediately jumps to the form in panel 5, with a vertical strut: the topology has changed. It retains this form as the height is further increased.

Now we reverse the process (see figure below): as the height is gradually decreased, the form of the soap film changes, but it maintains its topology until the shape passes beyond a square shape (panel 3). When the Steiner points coalesce (panel 4) the unstable solution jumps to a different topology, with a horizontal strut, and retains this form as the rectangle flattens further.

We notice that the solution assumed for four points in a square is dependent on the route through which the solution is reached. There is a hysteresis effect whereby, when the corner points move through a sequence of shapes and return to their original position, the final solution may be different from the initial one.

Computational Solutions

In 1968 Edgar Gilbert and Henry Pollak of Bell Laboratories published a comprehensive study, “Steiner Minimal Trees”. This set the scene for the development of fast numerical algorithms for solving the problem. According to Brazil, et al. (2014), this paper “helped to kindle a fascination with … [the Steiner] problem in the mathematical community that has lasted to the present day.”

In a few special cases, Steiner’s problem can be solved exactly. For a regular polygon with six or more sides, the polygon itself (less one edge) is the solution: the Steiner minimal tree coincides with the minimal spanning tree; no additional Steiner points are required. However, in general, we cannot obtain an analytical expression for the solution and must use numerical methods to find it.

For large n, the Steiner tree problem is computationally expensive (technically, it is NP-hard). To solve it, “heuristic methods” are used. These methods yield a solution that may not be optimal, but is close enough to be useful. Normally, they provide a solution that is within a few percent of the minimum solution. With heuristics, solution of the Steiner problem is computationally feasible for thousands of terminal points.

There is a variant of the Steiner problem, called the rectilinear Steiner problem, in which all the line segments must be either horizontal or vertical lines. This problem uses the so-called taxicab metric and is relevant for design of VLSI electric circuits.

The Gilbert-Pollak Conjecture for Steiner’s Ratio

The Steiner ratio is the ratio of the minimum Steiner tree length to the length of the minimum spanning tree with no additional (Steiner) points. Basically, it answers the question: By what factor can we reduce the length of a minimal spanning tree by introducing Steiner points?

For any finite set of points P, let LS(P) be the length of the Steiner minimum tree and LM(P) the length of the minimum spanning tree. Then we define the Steiner ratio to be

ρ = inf [ LS(P) / LM(P) ]

where the infimum is taken over all finite sets P of points in the plane. It was conjectured by Gilbert and Pollak (1968) that ρ = √3/2. A proof of this conjecture published in 1990 (Du and Hwang, 1990) attracted great media attention. It was reviewed in the New York Times, Science, the New Scientist and SIAM News.

However, a serious error was later found in the proof. There have been numerous papers published about this, a recent one being “Du-Hwang Characteristic Area: Catch-22” by Ivanov and Tuzhilin (2014). These authors conclude that, while the conjecture has been proved for n <= 8, the general case remains open.

References

♦ Brazil, M, R L Graham, D A Thomas and M Zachariasen, 2014: On the history of the Euclidean Steiner tree problem. Arch. Hist. Exact Sci., 68(3), 327–354.
♦ Courant, Richard and Herbert Robbins, 1941: What Is Mathematics? An Elementary Approach to Ideas and Methods. Paperback: Oxford University Press; 2 edition (July 18, 1996) . 592 pages. ISBN: 978-0195105193.
♦ Du, D-Z and F K Hwang, 1990: The Steiner ratio of Gilbert and Pollak is true. Proc. Natl. Acad. Sci., 87, 9464–9466.
♦ Ivanov, A O and A A Tuzhilin, 2014 : Du-Hwang Characteristic Area: Catch-22. ArXiV mathMG 1402.6079v1 (4 pages).