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

Du, D. Z.; Hwang, F. K.; Yao, E. Y.

J. Comb. Theory, Ser. A 38, 230-240 (1985).

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.

MSC:

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

Keywords:

ratio; Steiner minimal tree; minimal spanning tree

References:

[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