The Steiner ratio for five points (Q1179750)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The Steiner ratio for five points
scientific article

    Statements

    The Steiner ratio for five points (English)
    0 references
    0 references
    27 June 1992
    0 references
    A metric space \(M\) is considered. If \(P\) is a finite set of points of \(M\), then the Steiner minimal tree \(SMT(P)\) of \(P\) is the shortest connected network in \(M\) which contains all points of \(P\). The vertices of \(SMT(P)\) are points of \(P\) (regular points) and possibly also other points of \(M\) (Steiner points). The minimal spanning tree \(MST(P)\) of \(P\) is the shortest tree in \(M\) whose vertices are exactly all points of \(P\). Let \(L_ s(P)\) be the length (sum of lengths of edges) of \(SMT(P)\), let \(L_ m(P)\) be the length of \(MST(P)\). The Steiner ratio of \(M\) is \(\rho(M)=\inf\{L_ s(P)/L_ m(P)\mid P\subset M\}\). For the Euclidean plane E. N. Gilbert and H. O. Pollak have conjectured that \(L_ s(P)\geq(\sqrt 3/2)L_ m(P)\). For \(P\) having 5 points this was proved by D. Z. Du, E. Yao and F. K. Hwang. In this paper another proof is brought. The author writes: The present paper reproves the result for five points but, at the same time, it attempts to reduce the proof to the situation of many applications of some basic lemmas with, hopefully, a good prospect of generalizing to six or more points.
    0 references
    Steiner ratio
    0 references
    metric space
    0 references
    Steiner minimal tree
    0 references
    minimal spanning tree
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references