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.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s