Gradient-constrained minimum networks (II). Labelled or locally minimal Steiner points

A gradient-constrained minimum network T is a minimum length network, spanning a given set of nodes N in space with edges whose gradients are all no more than an upper bound m. The nodes in T but not in N are referred to as Steiner points. Such networks occur in the underground mining industry where the typical maximal gradient is about 1:7 (≈ 0.14). Because of the gradient constraint the lengths of edges in T are measured by a special metric, called the gradient metric. An edge in T is labelled as a b-edge, or an m-edge, or an f-edge if the gradient between its endpoints is greater than, or equal to, or less than m respectively. The set of edge labels at a Steiner point is called its labelling. A Steiner point s with a given labelling is called labelled minimal if T cannot be shortened by a label-preserving perturbation of s. Furthermore, s is called locally minimal if T cannot be shortened by any perturbation of s even if its labelling is not preserved. In this paper we study the properties of labelled minimal Steiner points, as well as the necessary and sufficient conditions for Steiner points to be locally minimal. It is shown that, with the exception of one labelling, a labelled minimal Steiner point is necessarily unique with respect to its adjacent nodes, and that the locally minimal Steiner point is always unique, even though the gradient metric is not strictly convex.     

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

Existence and regularity results for the Steiner problem

Given a complete metric space X and a compact set ${C\subset X}$ , the famous Steiner (or minimal connection) problem is that of finding a set S of minimum length (one-dimensional Hausdorff measure ${\mathcal H^1)}$ ) among the class of sets $$\mathcal{S}t(C) \,:=\{S\subset X\colon S \cup C \,{\rm is connected}\}.$$ In this paper we provide conditions on existence of minimizers and study topological regularity results for solutions of this problem. We also study the relationships between several similar variants of the Steiner problem. At last, we provide some applications to locally minimal sets.     

Separating subgraphs in k-trees: Cables and caterpillars

The class of k-trees has the property that the minimal sets of vertices separating two nonadjacent vertices u and v of a k-tree Q induce k-complete subgraphs. We show that the union T of these subgraphs belongs to a subclass of (k ? 1)-trees which generalizes caterpillars. The maximum order of a monochromatic set of vertices in the optimal coloring of this (k ? 1)-tree T determines the length of the minimal collection of k vertex-disjoint paths between the two vertices of Q, the u, v-cable, which is spanned on all vertices of T.     

Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

Approximations for two variants of the Steiner tree problem in the Euclidean plane {\mathbb{R}^2}

Given n terminals in the Euclidean plane and a positive constant l, find a Steiner tree T interconnecting all terminals with the minimum total cost of Steiner points and a specific material used to construct all edges in T such that the Euclidean length of each edge in T is no more than l. In this paper, according to the cost b of each Steiner point and the different costs of some specific materials with the different lengths, we study two variants of the Steiner tree problem in the Euclidean plane as follows: (1) If a specific material to construct all edges in such a Steiner tree has its infinite length and the cost of per unit length of such a specific material used is c ₁, the objective is to minimize the total cost of the Steiner points and such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_1+ c_1 \cdot \sum_{e \in T} w(e)\}}$ , where T is a Steiner tree constructed, k ₁ is the number of Steiner points and w(e) is the length of part cut from such a specific material to construct edge e in T, and we call this version as the minimum-cost Steiner points and edges problem (MCSPE, for short). (2) If a specific material to construct all edges in such a Steiner tree has its finite length L (l ≤ L) and the cost of per piece of such a specific material used is c ₂, the objective is to minimize the total cost of the Steiner points and the pieces of such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_2+ c_2 \cdot k_3\}}$ , where T is a Steiner tree constructed, k ₂ is the number of Steiner points in T and k ₃ is the number of pieces of such a specific material used, and we call this version as the minimum-cost Steiner points and pieces of specific material problem (MCSPPSM, for short). These two variants of the Steiner tree problem are NP-hard with some applications in VLSI design, WDM optical networks and wireless communications. In this paper, we first design an approximation algorithm with performance ratio 3 for the MCSPE problem, and then present two approximation algorithms with performance ratios 4 and 3.236 for the MCSPPSM problem, respectively.     

Minimum Networks for Four Points in Space

The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept — Simpson intersections, and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W.D. Smith and J.M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.     

On Urysohn’s ℝ-Tree

In the short note of 1927, Urysohn constructed the metric space R that is nowhere locally separable. There is no publication with indications that R is a (noncomplete) ?-tree that has valency c at each point. The author in 1989, as well as Polterovich and Shnirelman in 1997, constructed ?-trees isometric to R unaware of the paper by Urysohn. In this paper the author considers various constructions of the ?-tree R and of the minimal complete ?-tree of valency c including R, as well as the characterizations of ?-trees, their properties, and connections with ultrametric spaces.

     

Simple and exact formula for minimum loop length in Ate i pairing based on Brezing–Weng curves

We provide a simple and exact formula for the minimum Miller loop length in Ate _i pairing based on Brezing–Weng curves, in terms of the involved parameters, under a mild condition on the parameters. It will also be shown that almost all cryptographically useful/meaningful parameters satisfy the mild condition. Hence the simple and exact formula is valid for them. It will also turn out that the formula depends only on essentially two parameters, providing freedom to choose the other parameters to address the design issues other than minimizing the loop length.     

The steiner ratio conjecture is true for five points

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least $\text{3}\text{2}$. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. Recently, Du, Yao and Hwang used a different approach to give a shorter proof for n = 4. In this paper we continue this approach to prove the conjecture for n = 5. Such results for small n are useful in obtaining bounds for the ratio of the two lengths in the general case.     

The Steiner ratio conjecture for cocircular points

A Steiner minimal treeS is a network of shortest possible length connecting a set ofn points in the plane. LetT be a shortest tree connecting then points but with vertices only at these points.T is called a minimal spanning tree. The Steiner ratio conjecture is that the length ofS divided by the length ofT is at least 3/2. In this paper we use a variational approach to show that if then points lie on a circle, then the Steiner ratio conjecture holds.     

RIGIDITY AT INFINITY OF TREES AND EUCLIDEAN BUILDINGS

We show that if a group G acts isometrically on a locally finite leafless ?-tree inducing a two-transitive action on its ends, then this tree is determined by the action of G on the boundary. As a corollary we obtain that locally finite irreducible Euclidean buildings of dimension at least two are determined by their complete building at infinity.     

On extremal sizes of locally k-tree graphs

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n ²), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.     

Planar Manhattan Locally Minimal and Critical Networks

One-dimensional branching extremals of Lagrangian-type functionals are considered. Such extremals appear as solutions to the classical Steiner problem on a shortest network, i.e., a connected system of paths that has the smallest total length among all the networks spanning a given finite set of terminal points in the plane. In the present paper, the Manhattan-length functional is investigated, with Lagrangian equal to the sum of the absolute values of projections of the velocity vector onto the coordinate axes. Such functionals are useful in problems arising in electronics, robotics, chip design, etc. In this case, in contrast to the case of the Steiner problem, local minimality does not imply extremality (however, each extreme network is locally minimal). A criterion of extremality is presented, which shows that the extremality with respect to the Manhattan-length functional is a global topological property of networks. Bibliography: 95 titles.     

Steiner Trees on Curved Surfaces

 The Steiner tree problem on surfaces is more complicated than the corresponding one in the Euclidean plane. There are not many results on it to date. In this paper we first make a comparison of Steiner minimal trees on general curved surfaces with Steiner minimal trees in the Euclidean plane. Then, we focus our study on the Steiner trees on spheres. In particular, we detail the properties of locally minimal Steiner points, and the Steiner points for spherical triangles. Received: August 18, 1997 Final version received: March 16, 1998     

On the Cameron-Praeger conjecture

This paper takes a significant step towards confirming a long-standing and far-reaching conjecture of Peter J. Cameron and Cheryl E. Praeger. They conjectured in 1993 that there are no non-trivial block-transitive 6-designs. We prove that the Cameron-Praeger conjecture is true for the important case of non-trivial Steiner 6-designs, i.e. for 6-(v,k,λ) designs with λ=1, except possibly when the group is PΓL(2,pe) with p=2 or 3, and e is an odd prime power.     

A short proof of a result of Pollak on Steiner minimal trees

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least $\text{3}\text{2}$. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. However, the proof for n = 4 by Pollak is sufficiently complicated that no generalization to any other value of n has been found. We use a different approach to give a very short proof for the n = 4 case. This approach also allows us to attack the n = 5 case, though the proof is no longer short (to be reported in a subsequent paper).     

IP modeling of the survivable hop constrained connected facility location problem

We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least λ edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for finding its solution. Finally, we report computational results.     

Local convergence in Fermat's problem

The general Fermat problem is to find the minimum of the weighted sum of distances fromm destination points in Euclideann-space. Kuhn recently proved that a classical iterative algorithm converges to the unique minimizing point , for any choice of the initial point except for a denumerable set. In this note, it is shown that although convergence is global, the rapidity of convergence depends strongly upon whether or not  is a destination. If  is not a destination, then locally convergence is always linear with upper and lower asymptotic convergence boundsλ andλ′ (λ ≥ 1/2, whenn=2). If  is a destination, then convergence can be either linear, quadratic or sublinear. Three numerical examples which illustrate the different possibilities are given and comparisons are made with the use of Steffensen's scheme to accelerate convergence.     

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.