1. Euclidean and Minkowski Steiner Trees

The problem was suggested by Pierre de Fermat (1601–1665) in his celebrated essay on minima and maxima [152]: “Let he who does not approve of my method attempt the solution to the following problem: Given three points in the plane, find a fourth point such that the sum of its distances to the three given points is a minimum”. The earliest known solution to Fermat’s problem was a geometric construction due to the Italian physicist and mathematician Evangelista Torricelli (1608–1647) [371]. For a comprehensive study of the problem, see Kupitz and Martini [240].

The more usual term for this point is Fermat point or Fermat-Torricelli point, and for the more general case with n points minimising their distances to a single point, the point sought is also called the Steiner-Weber point. In this book we adopt the term Steiner point for all these cases, in order to emphasise the unity of this problem with the more general Steiner tree problems we discuss later. Essentially we are viewing the Fermat-Torricelli problem as the simplest non-trivial case of the Steiner tree problem.

This elegant construction is often attributed to Hofmann [200], but according to Honsberger [201, pp. 22–34], the Hungarian mathematician Tibor Gallai (1912–1992) discovered it independently. Some earlier attributions are mentioned in Kupitz and Martini [240], who name it the “rotation proof”. Presentations of the construction (and some generalisations) can be found in [125, 129, 184, 201, 222, 239].

Bonaventura Cavalieri (1598–1647), an Italian mathematician and Jesuate, argued that the segments connecting the given points with the Fermat-Torricelli point meet at 120^∘ angles. The fact that the Simpson lines, which connect the third corner of the equilateral triangle to the opposite given point, also meet at the Fermat-Torricelli point was shown in 1750 by Thomas Simpson (1710–1761). In 1834, Heinen [190] proved that the length of the Simpson lines are equal to the sum of distances from the given points to the Fermat-Torricelli point.

The earliest known statement and analysis of the Euclidean Steiner tree problem was by the French mathematician and logician Joseph Diaz Gergonne (1771–1859). In 1810 Gergonne established his own mathematics journal entitled the Annales de mathématiques pures et appliquées but more generally known as the Annales de Gergonne. In the first volume of the journal from 1810/11 [174], Gergonne states the following problem: “A number of cities are located at known locations on a plane; the problem is to link them together by a system of canals whose total length is as small as possible”. It is clear from the analysis that this is indeed the Euclidean Steiner tree problem, and Gergonne even proposes a method for solving the problem that basically is identical to Melzak’s algorithm from 1961 [277]. During the nineteenth century, three other statements of the problem were given by: Carl Friedrich Gauss (1777–1855) in a letter to Schumacher from March 19, 1836; Karl Bopp (1856–1905) in his dissertation [36] from 1879; and Eduard Hoffmann (1858–1923) in a celebration essay [199] from 1890. The first modern treatment of the problem was given by Vojtěch Jarník and Miloš Kössler in 1934 [223]. For a detailed account on the history of the Euclidean Steiner tree problem, see [47].

Minimum Steiner trees are more typically referred to as ‘Steiner minimum trees’ or ‘Steiner minimal trees’ in the literature. The main reason for this appears to be to give them an acronym ‘SMT’ that is different from that of a minimum spanning tree ‘MST’. Mathematically, however, the term ‘Steiner minimum tree’ does not make sense (what is a ‘minimum tree’ and how can it be Steiner?), and hence in this book we avoid it. In some of the early literature terminals were also referred to as ‘regular points’, but ‘terminal’ seems preferable as the word ‘regular’ is ambiguous and heavily used in other areas of mathematics.

We should note that this definition of a Steiner tree is different from the one in Gilbert and Pollak [179] and Hwang, Richards and Winter [211], but it is more operational.

A recursion was first given by Bopp [36] in 1879. Gilbert and Pollak [179] gave the same recursion and the formula; they credit Riordan [324] with solving the recursion. The proof that any Steiner topology can be realised by some minimum Steiner tree was first given by Hwang et al. [213].

The exponential but finite construction of Melzak [277] was given in 1961. Melzak’s algorithm was for a long time believed to be the first finite-time algorithm for solving the problem. More recently it has been discovered that Gergonne in 1810/11 [174] presented a solution method that basically is identical to the one suggested by Melzak 150 years later [47]. Hwang [210] improved the running time of Melzak’s original exponential algorithm to linear time. A number of implementation details were presented by Smith [351].

The Euclidean Steiner tree problem in the plane does, however, have a polynomial-time approximation scheme [16]. This means that for any fixed ε > 0 there exists a polynomial-time algorithm for computing a Steiner tree of length at most a factor 1 +ε from optimum.

Here we give a brief history of the Steiner ratio conjecture, based largely on the 2012 account by Ivanov and Tuzhilin [220], and their update in 2014 [221]. In 1992 a paper by Du and Hwang [135] presented a proof of the Steiner ratio conjecture. This proof, though generally accepted throughout most of the Steiner tree community, also caused some concern as the argument had a certain lack of precision and formality making it difficult to verify. The first paper to seriously question the proof in [135] was that of Yue [426], in 2000; however, the details of Yue’s criticism of the proof were unconvincing, and a proposed alternative proof was flawed. In 2001–2003 a number of mathematicians, including Ivanov, Tuzhilin, Morgan, Bern, Ceislik, Graham and others, discussed Du and Hwang’s proof via e-mail in some detail. Two major gaps were identified in the proof: one concerned the continuity of the inner spanning tree length and the other the reduction to full Steiner topologies. While some discussion of these gaps (by Ivanov and Tuzhilin) appeared in the Russian language literature at the time it was not until 2008 that these gaps were discussed in the English language mathematics literature, first by Ivanov and Tuzhilin [219], and shortly afterwards by de Wet [128] and Innami et al. [218]. The general consensus appears to be that there is no obvious way of fixing these gaps in the proof, hence the Steiner ratio conjecture remains open.

This invariance property for the minimal Steiner hull was first stated 10 years earlier in Part 1, Theorem 1.5 of the book [211] by Hwang et al. However, Winter [405] gives a simple counter-example to show that a key assumption in the ‘proof’ of this result in [211], that any pair of consecutive legal replacements can be directly reversed, is incorrect.

The terminology for a lune, which originated with Gilbert and Pollak [179] and is now standard in the Steiner tree literature, is inconsistent with the standard geometrical terminology. In planar geometry, the term ‘lune’ usually refers to a crescent-shaped convex-concave region bounded by two circular arcs, or in other words, the relative complement of one disc in another (where they intersect but neither is a subset of the other). A ‘lune’, as defined here, is an example of a ‘lens’ in standard planar geometry.

A slightly weaker version of Lemma 1.15, with the added assumption that two different full Steiner trees exist for N, was first proved by Pollak [305]. Du et al. [137] later simplified Pollak’s proof, and showed that the existence of a second full Steiner tree is not required. They also showed that it is possible for a full Steiner tree of N that is not acute to be a minimum Steiner tree (if no other full Steiner tree exists).

Cockayne and Schiller [115] developed the first computer code to compute minimum Steiner trees in 1972. The computer program enumerated terminal subsets and full Steiner topologies for each subset, and used Melzak’s algorithm [277] to compute a full Steiner tree for a given full Steiner topology. The constructed full Steiner trees were then combined to form a minimum Steiner tree. Improved implementations of the algorithm were suggested by Boyce and Seery [39] and Boyce [38]. None of these implementations were able to compute minimum Steiner trees for more than 10 terminals. Winter [402] suggested the GeoSteiner approach in 1985, allowing the computation of minimum Steiner trees with more than 20 terminals. Cockayne and Hewgill [112, 113] suggested a number of improvements to Winter’s algorithm that allowed the computation of minimum Steiner trees with up to 50 terminals.

This use of the term “fulsome” is unfortunate, as the usual English meaning of the word is ‘excessive’ or ‘insincere’. However, since the publication of [211] the term has become standard.

This terminology is taken from [358].

Theorem 1.27 was first stated by Cockayne [110], but without a complete proof. Full proofs were given by Levy [252] and Alfaro et al. [7], before the rather more elegant and general proof given by Lawler and Morgan [241].

The approach here is loosely based on that outlined in [80] for the more restricted problem where the Minkowski norm has a strictly convex and differentiable unit circle. More details on the proof of this restricted problem, based on the method of Lagrange Multipliers, have also appeared in [176].

Such an edge e is referred to elsewhere in the literature [353] as a trombone wire. The slide described here is an example of a zero-shift, which we study in more detail in Chap. 2.

For more details on the early history of the Euclidean Steiner tree problem, see [47]. One of the few modern papers further exploring the potential of the Euclidean Steiner tree problem in the design of road networks is the work of Stückelberger et al. [357].

Employees or associates of Bell Laboratories who made important early contributions to the Euclidean Steiner tree problem in the plane include Zdzislaw Melzak [277], Edgar Gilbert [178], Henry Pollak [179], and Ronald Graham and Frank Hwang [183].

Karl Bopp’s publication on Steiner trees took the form of a dissertation entitled “On the shortest connection system for four points” [36]. As the title suggests, the work considers the problem of how to construct a minimum Euclidean Steiner tree on four terminals. Although most of the focus is on the planar case, the thesis concludes with some brief observations on the three-dimensional problem, and states (without proof) some of the fundamental properties of three-dimensional Euclidean Steiner trees. These properties were proved and generalised to d-dimensional space (for all integers d ≥ 2) in 1934 by the Czech mathematicians Jarník and Kössler [223], who were almost certainly unaware of Bopp’s earlier work. This paper fell into obscurity until it was eventually rediscovered in the 1970s. Higher dimensional Steiner trees were not studied again in the literature until the seminal paper of Gilbert and Pollak [179] in 1968, where there is a short discussion of the three-dimensional problem.

This non-computability result was first given by Smith [351], however the counter-example derived in that paper is difficult to verify. A clearer, more elegant counter-example was given by St. Mehlhos [276], who was apparently unaware of Smith’s paper. An easier method for constructing counter-examples was later devised by Rubinstein et al. [329].