Vertex degrees of Steiner minimal trees in _p^d and other smooth Minkowski spaces

DOI10.1007/PL00009431MaRDI QIDQ1289246zbMATH OpenOpenAlexFDO

Authors Konrad J. Swanepoel

Publication date 29 September 1999

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.0443

zbMATH Keywords

Banach spacesmooth Minkowski spacesSteiner minimal treeSteiner point

Mathematics Subject Classification ID

Trees (05C05) Geometry and structure of normed linear spaces (46B20)

Abstract: We find upper bounds for the degrees of vertices and Steiner points in Steiner Minimal Trees in the d-dimensional Banach spaces ell_p^d independent of d. This is in contrast to Minimal Spanning Trees, where the maximum degree of vertices grows exponentially in d (Robins and Salowe, 1995). Our upper bounds follow from characterizations of singularities of SMT's due to Lawlor and Morgan (1994), which we extend, and certain ell_p-inequalities. We derive a general upper bound of d+1 for the degree of vertices of an SMT in an arbitrary smooth d-dimensional Banach space; the same upper bound for Steiner points having been found by Lawlor and Morgan. We obtain a second upper bound for the degrees of vertices in terms of 1-summing norms.

Review text

Given a finite-dimensional Banach space. For a finite set \(S\) of points in this space a Steiner minimal tree \(T\) for \(S\) is a tree interconnecting \(S\) such that the total length of \(T\) is minimal among all trees on \(S\). The vertices of \(V(T)\setminus S\) are called Steiner points. It is well known that there are upper bounds for the degrees of the vertices in a Steiner minimal tree where these quantities depend only on the space. The paper investigates the geometry of \(d\)-dimensional Banach spaces \(X\), to find the values \(s(X)\) and \(v(X)\) for the largest degree of a Steiner point and a vertex, respectively. Particularly, it is shown that (1) \(3\leq s(X)\leq v(X)\leq d+1\) holds in a smooth space of dimension at least 2, and (2) in a space normed by a \(p\)-norm, \(p\geq 2\), the quantities \(s(X)\) and \(v(X)\) are relatively small and independent of the dimension of the space.

Cited in

(7)

• Sets of unit vectors with small subset sums
• Quantitative Illumination of Convex Bodies and Vertex Degrees of Geometric Steiner Minimal Trees
• scientific article; zbMATH DE number 4156455 (Why is no real title available?)
• scientific article; zbMATH DE number 7529 (Why is no real title available?)
• scientific article; zbMATH DE number 866020 (Why is no real title available?)
• The Gilbert arborescence problem
• The local Steiner problem in finite-dimensional normed spaces

This page was built for publication: Vertex degrees of Steiner minimal trees in \(\ell_p^d\) and other smooth Minkowski spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1289246)