The Steiner ratio conjecture is true for five points
type: Item
instance of: scholarly article
title: The Steiner ratio conjecture is true for five points
zbMATH Open document ID: 0576.05015
DOI: 10.1016/0097-3165(85)90073-1
author: B. George
published in: Journal of Combinatorial Theory. Series A
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 51M15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3920489
zbMATH Keywords: ratio
zbMATH Keywords: Steiner minimal tree
zbMATH Keywords: minimal spanning tree
Wikidata QID: Q122987645
MaRDI profile type: Publication
full work available at URL: 0097-3165(85)90073-1
OpenAlex ID: W2088497613
cites work: A Lower Bound for the Steiner Tree Problem
cites work: A New Bound for the Steiner Ratio
cites work: A short proof of a result of Pollak on Steiner minimal trees
cites work: Steiner Minimal Trees
cites work: On the Problem of Steiner
cites work: Some remarks on the Steiner problem
description: scientific article; zbMATH DE number 3920489