Home » Discrete Geometry » The Steiner problem in normed spaces III

# The Steiner problem in normed spaces III

Also see Part I and Part II.

### The formulation

Finally, let’s make a precise formulation of the Local Steiner problem. There are two types of vertices in a Steiner tree, the given points or terminals, and the Steiner points. The collection of edges emanating from a terminal is called a terminal configuration, and from a Steiner point a Steiner configuration. Clearly, if $x$ is a Steiner point in a SMT with incident edges $xv_i$, $i=1,\dots,n$, then the star consisting of vertices $\{x,v_1,\dots,v_n\}$ and edges $\{xv_i:i=1,\dots,n\}$ is a SMT of $\{v_1,\dots,v_n\}$. (A similar statement can be formulated for terminals.)
Thus we only have to consider stars. Without loss of generality, the centre $x$ of the star may be taken to be the origin $o$. We may also assume that all the edges incident to $o$ are of unit length: first scale the star so that all edges are larger than unit length; then it is clear that the star from $o$ to all points on the edges at distance 1 from $o$ must also be a SMT. Note that Steiner configurations form a subclass of terminal configurations. Indeed, if the star with edges $ov_i$ is a SMT of $\{v_1,\dots,v_n\}$, then it is also a SMT of $\{o,v_1,\dots,v_n\}$.

The local Steiner problem. Given a finite-dimensional normed space $(X,\|\cdot\|)$, characterize all collections of unit vectors $\{v_1,\dots,v_n\}$

• that form a terminal configuration, i.e., such that the star from $o$ to the $v_i$ is a SMT of $\{o,v_1,\dots,v_n\}$, or
• that form a Steiner configuration, i.e., such that the star from $o$ to the $v_i$ is a SMT of $\{v_1,\dots,v_n\}$.

As an example, the solution in Euclidean space $\ell_2^d$ is the following:

$\{v_1,\dots,v_n\}$ forms

• a terminal configuration if, and only if, $n\leq 3$ and all angles $\sphericalangle v_i o v_j\geq 120^\circ$;
• a Steiner configuration if, and only if, $n= 3$ and all angles $\sphericalangle v_i o v_j= 120^\circ$.

In other normed spaces, our study of this problem utilizes various interesting fields of mathematics, in particular

1. Convexity: covering and illumination of convex bodies,
2. Convex Analysis: the subdifferential calculus,
3. Combinatorics: extremal finite set theory,
4. Banach space theory and linear algebra: Cotype and 1-summing constants

Thus this problem is not only of interest in itself. Instead, the connections to different fields of geometry and analysis enhances its importance.

### Two guiding conjectures

Let $\tau(X)$ [$\sigma(X)$, resp.] denote the maximum degree of a terminal [Steiner point, resp.] in a SMT in the normed space $X$, where the maximum is taken over all SMTs. These two values measure what may be called the local complexity of a SMT in $X$. A natural question is to determine these values for a given space $X$. This should be possible in principle once the local Steiner problem is solved for $X$. Observe that, since Steiner configurations are also terminal configurations, $\sigma(X)\leq \tau(X)$.

Morgan’s conjecture

Frank Morgan (1992, 1998 ) made the following conjecture:

Conjecture. For any $d$-dimensional normed space $X$, $\sigma(X)\leq 2^d$.

It is not difficult to show that $\sigma(\ell_\infty^d)=2^d$. Indeed, the star joining the origin to the $2latex ^d$ vertices of the unit ball is a SMT of the vertices. Thus the upper bound of $2^d$, if true, would be best possible. However, at least when $d=2$, there are other norms also attaining $2^d$ (Alfaro et al.1991).

In 2000 I showed that this conjecture holds for $d=2$, and I characterized all the 2-dimensional $X$ with $\sigma(X)=4$.

Cieslik’s conjecture

Dietmar Cieslik (1990, 1998 ) made a conjecture analogous to ‘s conjecture for $\tau(X)$.

Conjecture. For any $d$-dimensional normed space $X$, $\tau(X)\leq 2(2^d-1)$. Equality holds for the $d$-dimensional space $Z^d$ with unit ball $\mathrm{conv}([-1,0]\cup[0,1]^d)$.

Cieslik (1990b) proved this conjecture for the case $d=2$, where the unit ball is an affine regular hexagon. The unit ball of $Z^3$ is affinely equivalent to the rhombic dodecahedron.

### References

• M. Alfaro, M. Conger, K. Hodges, A. Levy, R. Kochar, L. Kuklinski, Z. Mahmood, and K. von Haam, The structure of singularities in $\Phi$-minimizing networks in $\mathbf{R}^2$, Pacific J. Math. 149 (1991), 201-210.
• D. Cieslik, Knotengrade kürzester Bäume in endlich-dimensionalen Banachräumen, Proceedings of the 7th Fischland Colloquium, II (Wustrow, 1988), no. 39, 1990, pp. 89-93.
• D. Cieslik, The vertex-degrees of Steiner minimal trees in Minkowski planes, Topics in Combinatorics and Graph Theory (R. Bodendiek and R. Henn, eds.), Physica-Verlag, Heidelberg, 1990, pp. 201-206.
• D. Cieslik, Steiner minimal trees, Nonconvex Optimization and its Applications, vol.23, Kluwer Academic Publishers, Dordrecht, 1998.
• F. Morgan (2000), Geometric measure theory, third ed., Academic Press Inc., San Diego, CA, 2000.
• F. Morgan (1992), Minimal surfaces, crystals, shortest networks, and undergraduate research, Math. Intelligencer 14, 37-44.
• F. Morgan (2000), Geometric measure theory, third ed., Academic Press Inc., San Diego, CA, 2000.
• F. Morgan (1992), Minimal surfaces, crystals, shortest networks, and undergraduate research, Math. Intelligencer 14, 37-44.