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

The Steiner problem in normed spaces II

Other norms

In part I I discussed the Steiner problem in the Euclidean plane. Here I give an overview of various normed spaces for which geometric Steiner minimal trees have been considered. This motivates the study of Steiner minimal trees in arbitrary (finite-dimensional) normed spaces.

A finite-dimensional normed space (or Minkowski space) is a finite-dimensional real vector space X on which a norm has been defined, i.e., a function \|\cdot\|:X\to\mathbb{R} such that

  • \|x\|\geq 0 for all x\in X with equality only for x=o;
  • \|\lambda x\|=|\lambda|\|x\| for all \lambda\in\mathbb{R} and x\in X; and
  • \|x+y\|\leq\|x\|+\|y\| for all x,y\in X.

Higher dimensional Euclidean spaces

Mimura (1933) and Jarník and Kössler (1934) were among the first to consider Steiner minimal trees in Euclidean spaces (see also Korte and Nesetril 2001 for more history). Recently, attemps have been made to use high-dimensional Euclidean spaces to model phylogenetic trees (Brazil et al. 2008).

\lambda-geometry

Motivated by application in engineering, Hanan (1966) considered Steiner minimal trees in the \ell_1-plane, i.e., \ell_1^2:=(\mathbb{R}^2,\|\cdot\|_1), where \|(x,y)\|_1:=|x|+|y|. This is the distance between two points if one is only allowed to use vertical and horizontal lines. This norm is the main norm used in VLSI design. Recently, more orientations have also been considered. For example, if we allow three orientations, each at 60^\circ with respect to the other, we obtain the norm in which the unit ball is a regular hexagon. With four orientations, each at 45^\circ degrees, we obtain the norm with unit ball a regular octagon. In general we may consider the so-called \lambda-geometry, where the unit ball is the regular polygon with 2\lambda sides inscribed in the Euclidean circle. For even more general considerations, see for example Yan et al. (1997).

\ell_p norm

The $\ell_p$ norm is very important in analysis, and has been considered in the Location Science literature to model distances between cities (Brimberg et al. 1991, 1993, Drezner et al. 2002). Weng (2008) uses this norm in the study of phylogenetic trees. The \ell_p norm generalizes both the Euclidean norm and the \ell_1 norm. For 1<p<\infty it is defined on \mathbb{R}^d as

\|(x_1,\dots,x_d)\|_p := (\sum_{i=1}^d|x_i|^p)^{1/p},

and for $p=\infty$ as

\|(x_1,\dots,x_d)\|_{\infty} := \max\{|x_i|:i=1,\dots,d\}.

Gradient-constrained norm

The next example comes from the underground mining industry (Brazil et al. 1998, 2001). Here the problem is to design a network of tunnels connecting a set of given underground locations where ore is concentrated. Because of limitations in the trucks used to haul the ore, the tunnels are not allowed to be too steep. Thus we constrain the gradient of each edge to be at most m, say. Apart from this constraint, the distance is Euclidean.

This distance function has the following formula, which satisfies the norm axioms.

\|(x,y,z)\| := \sqrt{x^2+y^2+z^2} if |z|\leq m\sqrt{x^2+y^2}, and \|(x,y,z)\| := \sqrt{1+m^{-2}}|z| if |z|\geq m\sqrt{x^2+y^2}.

The unit ball is the Euclidean unit ball with the north and south poles sliced off.


The one-dimensional Plateau problem

One viewpoint, which originates in the theory of minimal surfaces, is to consider Steiner minimal trees as the lowest dimensional case of the general Plateau problem. This is the problem of finding a set of smallest measure that makes a given set more connected. The classical Plateau problem is to find a surface in \mathbb{R}^3 of smallest area which closes a given Jordan arc in 3-space. Here the study of singularities is very important, as they form an obstacle in getting a mathematical grip on minimizers (Morgan 2000). Similarly, the Euclidean Steiner problem is to find a network of smallest length which connects a given set of points. These consideration lead Frank Morgan and his students to study the local structure of Steiner minimal trees for various norms. They were mostly interested in piecewise-C^\infty or uniformly convex norms (i.e., the curvature of the boundary of the unit ball is bounded away from 0). See Morgan (1992) for an exposition.

In the next installment, I’ll introduce the local Steiner problem.

References

  • Y. Mimura (1933), Über die Bogenlänge, Ergebnisse eines Mathematischen Kolloquiums (K. Menger, ed.), vol. 4, Teubner, Leipzig und
    Wien, pp.~20–22.
  • V. Jarník and M. Kössler (1934), O minimalnich grafeth obeahujicich n danijch bodu, Cas. Pest. Mat. Fys. 63, 223-235.
  • B. Korte and J. Nesetril (2001), Vojtech Jarník’s work in combinatorial optimization, Discrete Math. 235, 1-17.
  • M. Brazil, B.K. Nielsen, D.A. Thomas, and M. Zachariasen (2008), A novel approach to phylogenetic trees: d-dimensional geometric Steiner trees,
    Networks, to appear.
  • M. Hanan (1966), On Steiner’s problem with rectilinear distance, SIAM J. Appl. Math. 14, 255-265.
  • G. Y. Yan, A. Albrecht, G. H. F. Young, and C. K. Wong (1997), The Steiner tree problem in orientation metrics, J. Comput. System Sci. 55, 529-546.
  • J. Brimberg and R. F. Love (1991), Estimating travel distances by the weighted \ell\sb p norm, Nav. Res. Logist. 38, 241-259
  • J. Brimberg and R. F. Love (1993), Global convergence of a generalized iterative procedure for the minisum location problem with \ell\sb p distances, Oper. Res. 41, 1153-1163.
  • Z. Drezner and G. O. Wesolowsky (2002), Sensitivity analysis to the value of p of the \ell_p distance Weber problem, Ann. Oper. Res. 111, 135-150.
  • M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald (2001), Gradient-constrained minimum networks. I. Fundamentals, J. Global Optim. 21, 139-155.
  • 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

One thought on “The Steiner problem in normed spaces II

  1. Pingback: The Steiner problem in normed spaces III « Konrad Swanepoel’s blog

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