Minimum Steiner trees in normed planes
A compact, convex and centrally symmetric domain \(D\) in the Euclidean plane defines a norm establishing a metric in this plane which makes the plane a normed plane. A minimum Steiner tree (SMT) for a given finite set \(X\) of points in such a plane is a network interconnecting the points of \(X\) having minimum possible total length \(L_ s(X)\). It is given the following fundamental property: If the boundary of \(D\) is differentiable and strictly convex, then every full SMT (that means a SMT with exactly \(2| X|-2\) vertices) consists of three sets of parallel segments. The main subject of the paper is the study of the Steiner ratio \(\rho(D)\) defined by \(\rho(D)=\inf\{L_ S(X)/L_ M(X)\): \(X\) a finite set in the normed plane with domain \(D\}\), where \(L_ M(X)\) is the length of a minimum spanning tree for \(X\). Improving a prior result by the reviewer (see \textit{D. Cieslik} [Contemporary methods in graph theory. In honour of Prof. Dr. K. Wagner, 231-247 (1990; Zbl 0755.51006)]) it is shown that the Steiner ratio for each normed plane lies between 0.623 and 0.8686.
scientific article; zbMATH DE number 203061