The Steiner ratio conjecture is true for five points. (English) Zbl 0576.05015

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal spanning tree is at least \(\sqrt{3}/2\). This conjecture has been shown to be true for \(n=3\) by Gilbert and Pollak, and for \(n=4\) by Pollak. Recently, the autors used a different approach to give a shorter proof for \(n=4\). In this paper, we continue this approach to prove the conjecture for \(n=5\). Some results are useful in obtaining bounds for the ratio of two lengths in the general case. Let L(AB) denote the Euclidean distance between two points A and B and define \(L(A_ 1A_ 2...A_ n)=L(A_ 1A_ 2)+L(A_ 2A_ 3)+...+L(A_{n-1}A_ n)\). For a sequence of points \(A_ 1,A_ 2,...,A_ n\), let \(\sphericalangle A_ i\) denote the angle \(\sphericalangle A_{i-1}A_ iA_{i+1}\), the angle from line \([A_{i- 1},A_ i]\) to line \([A_{i+1},A_ i]\). The main lemma is that suppose that \(k\cdot 180-60\leq \sum^{j+k-1}_{i=j}\sphericalangle A_ i\leq k\cdot 180+60\), \(j=1,2,...,n-1\), \(k=1,2,...,n-j\), then \(L(A_ 1A_ n)\geq (\sqrt{3}/2)L(A_ 1A_ 2...A_ n).\)
By Melzak’s method, a Steiner minimal tree can be transfered into a segment and every spanning tree can be transfered into a path interconnecting two endpoints of the segment. By a case argument on angles, we proved that there always exists a spanning tree path which satisfies the condition of the main lemma, for \(n=5\). The same idea would work for \(n=6\). The same idea would work for \(n=6\). However, the argument becomes too complicated to be written down.


05C05 Trees
51M15 Geometric constructions in real or complex geometry
05C35 Extremal problems in graph theory
Full Text: DOI


[1] Chung, F.R.K; Hwang, F.K, A lower bound for the Steiner tree problem, SIAM J. appl. math., 34, 27-36, (1978) · Zbl 0376.05020
[2] Du, D.Z; Hwang, F.K, A new bound for the Steiner ratio, Trans. amer. math. soc., 278, 137-148, (1983) · Zbl 0523.51017
[3] Du, D.Z; Yao, E.Y; Hwang, F.K, A short proof of a result of pollak on Steiner minimal trees, J. combin. theory ser. A, 32, 396-400, (1982) · Zbl 0507.05028
[4] Gilbert, E.N; Pollak, H.O, Steiner minimal trees, SIAM J. appl. math., 16, 1-29, (1968) · Zbl 0159.22001
[5] Melzak, Z.A, On the problem of Steiner, Canad. math. bull., 4, 143-148, (1961) · Zbl 0101.13201
[6] Pollak, H.O, Some remarks on the Steiner problem, J. combin. theory ser. A, 24, 278-295, (1978) · Zbl 0392.05021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.