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.

Written by konradswanepoel

2nd September 2008 at 6.53 am

Posted in Discrete Geometry, Steiner trees

Tagged with Add new tag

One Response

Subscribe to comments with RSS.

[...] 24 October 2008 in Discrete Geometry, Steiner trees | Tags: Steiner minimal trees Also see Part I and Part II. [...]

The Steiner problem in normed spaces III « Konrad Swanepoel’s blog

24th October 2008 at 2.12 pm

Reply

Geometry and Combinatorics