On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

The Steiner ratio of several discrete metric spaces

Steiner's Problem is the “Problem of shortest connectivity”, that means, given a finite set of points in a metric space (X,ρ), search for a network interconnecting these points with minimal length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. If we do not allow Steiner points, that means, we only connect certain pairs of the given points, we get a tree which is called a Minimum Spanning Tree (MST). Steiner's Problem is very hard as well in combinatorial as in computational sense, but, on the other hand, the determination of an MST is simple. Consequently, we are interested in the greatest lower bound for the ratio between the lengths of these both trees:

which is called the Steiner ratio (of (X,ρ)). We look for estimates and exact values for the Steiner ratio in several discrete metric spaces. Particularly, we determine the Steiner ratio for spaces of words, and we estimate the Steiner ratio for specific graphs.     

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 Steiner Trees with Minimum Number of Steiner Points

Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.     

Gradient-Constrained Minimum Networks. III. Fixed Topology

The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).     

Two Heuristics for the Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each. We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

Minimal curvature-constrained networks

This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon.     

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.     

The steiner ratio for five points

It was conjectured by Gilbert and Pollak [5] that for any finite set of points in the Euclidean plane, the ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree is at least 3/2. The present paper proves the conjecture for five points, using a formula for the length of full Steiner trees.     

Gradient-constrained minimum networks. I. Fundamentals

In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value m. A gradient-constrained minimum Steiner tree T is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than m. We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in T is either three or four. If the edges in T are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to m, then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in T. Moreover, we prove that all four edges incident with a degree 4 Steiner point in T must have gradient m if m is less than 0.38. Finally, we use the variational argument to locate the Steiner points in T in terms of the positions of the neighbouring vertices.     

Approximate Euclidean Steiner Trees

An approximate Steiner tree is a Steiner tree on a given set of terminals in Euclidean space such that the angles at the Steiner points are within a specified error from \(120^{\circ }\). This notion arises in numerical approximations of minimum Steiner trees. We investigate the worst-case relative error of the length of an approximate Steiner tree compared to the shortest tree with the same topology. It has been conjectured that this relative error is at most linear in the maximum error at the angles, independent of the number of terminals. We verify this conjecture for the two-dimensional case as long as the maximum angle error is sufficiently small in terms of the number of terminals. In the two-dimensional case we derive a lower bound for the relative error in length. This bound is linear in terms of the maximum angle error when the angle error is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error in length for larger values of the maximum angle error and calculate exact values in the plane for three and four terminals.     

Rotationally optimal spanning and Steiner trees in uniform orientation metrics

We consider the problem of finding a minimum spanning and Steiner tree for a set of n points in the plane where the orientations of edge segments are restricted to λ uniformly distributed orientations, λ=2,3,4,… , and where the coordinate system can be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when λ=2 or λ=4. In the former, so-called rectilinear case, the edge segments have to be parallel to one of the coordinate axes, and in the latter, so-called octilinear case, the edge segments have to be parallel to one of the coordinate axes or to one of the lines making 45° with the coordinate axes (so-called diagonals). As the coordinate system is rotated—while the points remain stationary—the length and indeed the topology of the minimum spanning or Steiner tree changes. We suggest a straightforward polynomial-time algorithm to solve the rotational minimum spanning tree problem. We also give a simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting, and a finite time algorithm for the general Steiner tree problem with λ uniform orientations. Finally, we provide some computational results indicating the average savings for different values of n and λ both for spanning and Steiner trees.     

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.     

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

A simple proof of Hwang's theorem for rectilinear Steiner minimal trees

We present a simple, direct proof of Hwang's characterization of rectilinear Steiner minimal trees [3]: LetS be a set of at least five terminals in the plane. If no rectilinear Steiner minimal tree forS has a terminal of degree two or more, there is a tree in which at most one of the Steiner points does not lie on a straight linel, and the tree edges incident to the Steiner points onl appear on alternate sides. This theorem has been found useful in proving other results for rectilinear Steiner minimal trees.     

Converting triangulations to quadrangulations

We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such as a polygon, set of points, line segments or planar subdivision) admits a quadrangulation without the use of Steiner points, or with a bounded number of Steiner points. We also investigate the effect of demanding that the Steiner points be added in the interior or exterior of a triangulated simple polygon and propose efficient algorithms for accomplishing these tasks. For example, we give a linear-time method that quadrangulates a triangulated simple polygon with the minimum number of outer Steiner points required for that triangulation. We show that this minimum can be at most n/3, and that there exist polygons that require this many such Steiner points. We also show that a triangulated simple n-gon may be quadrangulated with at most n/4 Steiner points inside the polygon and at most one outside. This algorithm also allows us to obtain, in linear time, quadrangulations from general triangulated domains (such as triangulations of polygons with holes, a set of points or line segments) with a bounded number of Steiner points.     

Rectilinear group Steiner trees and applications in VLSI design

 Given a set of disjoint groups of points in the plane, the rectilinear group Steiner tree problem is the problem of finding a shortest interconnection (under the rectilinear metric) which includes at least one point from each group. This is an important generalization of the well-known rectilinear Steiner tree problem which has direct applications in VLSI design: in the detailed routing phase the logical units typically allow the nets to connect to several electrically equivalent ports. We present a first (tailored) exact algorithm for solving the rectilinear group Steiner tree problem (and related variants of the problem). The algorithm essentially constructs a subgraph of the corresponding Hanan grid on which existing algorithms for solving the Steiner tree problem in graphs are applied. The reductions of the Hanan grid are performed by applying point deletions and by generating full Steiner trees on the remaining points. Experimental results for real-world VLSI instances with up to 100 groups are presented. Received: November 7, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002     

Analytic formulas for full steiner trees

It was conjectured by Gilbert and Pollak [6] that, for any finite set of points in the Euclidean plane, the ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree is at least . To date, this has been proved only for at most five points. In this paper, some analytic formulas for the length of full Steiner trees are considered. These provide an alternative proof of the conjecture for quadrilaterals, and the foundation for a possible approach for more complicated polygons.     

Minimum steiner trees in normed planes

A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the unit disk is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratio(D) forD, and show that, for anyD, 0.623<(D)<0.8686.Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648.     

The role of Steiner hulls in the solution to Steiner tree problems

ASteiner tree problem on the plane is that of finding a minimum lengthSteiner tree connecting a given setK ofterminals and lying within a given regionR of the Euclidean plane; it includes as special cases the Euclidean Steiner minimal tree problem (ESMT), the rectilinear Steiner tree problem (RST), and the Steiner tree problem on graphs (STG). ASteiner hull forK inR generically refers to any subregion ofR known to contain a Steiner tree. This paper gives a survey of the role of Steiner hulls in the Steiner tree problem. The significance of Steiner hulls in the efficient solution of Steiner tree problems is outlined, and then a compendium is given of the known Steiner hull constructions for ESMT, RST, and STG problems.