Minimum Steiner trees in normed planes
type: Item
instance of: scholarly article
title: Minimum Steiner trees in normed planes
zbMATH Open document ID: 0774.05028
DOI: 10.1007/BF02189328
author: Du Ding-Zhu
author: Biao Gao
author: Ron Graham
author: Zicheng Liu
author: Peng-Jun Wan
published in: Discrete \& Computational Geometry
publication date: 1993-06-16T00:00:00Z
full work available at URL: https://eudml.org/doc/131252
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52A21
zbMATH DE Number: 203061
zbMATH Keywords: minimum Steiner tree
zbMATH Keywords: Steiner ratio
zbMATH Keywords: normed plane
reviewed by: Dietmar Cieslik
MaRDI profile type: Publication
cites work: The structure of singularities in \(\Phi\)-minimizing networks in \({\mathbb{R}}^ 2\)
cites work: The Fermat problem in Minkowski spaces
cites work: On the Steiner Problem
cites work: A proof of the Gilbert-Pollak conjecture on the Steiner ratio
cites work: Reducing the Steiner Problem in a Normed Space
cites work: The Complexity of Computing Steiner Minimal Trees
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Steiner Minimal Trees
cites work: On Steiner Minimal Trees with Rectilinear Distance
cites work: Paired calibrations applied to soap films, immiscible fluids, and surfaces or networks minimizing other norms
cites work: On Steiner minimal trees with \(L_ p\) distance
cites work: Q4097206
cites work: Locating the vertices of a steiner tree in an arbitrary metric space
Recommended article: On Steiner minimal trees with \(L_ p\) distance
Recommended article: A tight lower bound for the Steiner ratio in Minkowski planes
Recommended article: On Steiner ratio conjectures
Recommended article: Q4027152
Recommended article: Q4329126
Recommended article: Q3484850
Recommended article: Q4527177
Recommended article: Q3972515
Recommended article: Q4234114
Recommended article: Q3970498
description: scientific article; zbMATH DE number 203061