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 on which a norm has been defined, i.e., a function such that
- for all with equality only for ;
- for all and ; and
- for all .
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).
Motivated by application in engineering, Hanan (1966) considered Steiner minimal trees in the -plane, i.e., , where . 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 with respect to the other, we obtain the norm in which the unit ball is a regular hexagon. With four orientations, each at degrees, we obtain the norm with unit ball a regular octagon. In general we may consider the so-called -geometry, where the unit ball is the regular polygon with sides inscribed in the Euclidean circle. For even more general considerations, see for example Yan et al. (1997).
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 norm generalizes both the Euclidean norm and the norm. For it is defined on as
and for $p=\infty$ as
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 , say. Apart from this constraint, the distance is Euclidean.
This distance function has the following formula, which satisfies the norm axioms.
if , and if .
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 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- 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.
- Y. Mimura (1933), Über die Bogenlänge, Ergebnisse eines Mathematischen Kolloquiums (K. Menger, ed.), vol. 4, Teubner, Leipzig und
- V. Jarník and M. Kössler (1934), O minimalnich grafeth obeahujicich 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 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 distances, Oper. Res. 41, 1153-1163.
- Z. Drezner and G. O. Wesolowsky (2002), Sensitivity analysis to the value of of the 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.