- Journal Article
The Steiner ratio conjecture of Gilbert and Pollak states that for any set of n 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 √3/2. This is shown to be true for n = 3 by Gilbert and Pollak [SIAM J. Appl. Math., 16 (1968), pp. 1–29], for n = 4 by Pollak [J. Combin. Theory Ser. A, 24 (1978), pp. 278–295], and for n = 5 by Du, Hwang, and Yao [J. Combin. Theory Ser. A, 38 (1985), pp. 230–240]. In this paper a simple and powerful approach is used to prove the conjecture for n = 5 by arguing simultaneously with minimal spanning trees and Steiner minimal trees. Show more
Journal / seriesSIAM Journal on Applied Mathematics
Pages / Article No.
SubjectSteiner minimal tree; Steiner ratio
Organisational unit03340 - Widmayer, Peter / Widmayer, Peter
MoreShow all metadata