Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low tot al edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, D-66123 Saarbrucken, Germany. Email: {arya, michiel}@mpi-sb. mpg. de. Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM 11). t Math Sciences Dept., The University of Memphis, Memphis, TN 38152. Supported in part by NSF Grant CCR9306822. E-mail: dasg@next 1.msci .memst . edu. i Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland. Partially supported by NSF Grant CCR-93107O5. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: mount @cs. umd. edu. SQue~Tech, IIIC., 7600A Leesburg Pike, Falls Church, VA 22043. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: jsalowet!nvl, army .mil. Permission to copy without fee all or part of thk material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyri ht notice and the title of thq publication and, is date appear, a#notice is given that copyt~isby~n,sslon of the Ass@ationof Computing Machinery. o cop otherwise, or to republish, requires a fee ancf/or speci ic permission. STOC’ 95, Las Vegas, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 properties. We achieve these results in large part because of a new structure, called the dumbbell tree which provides a method of decomposing a spanner into a constant number of trees, so that each of the O(n2) spanner paths is mapped entirely to a path in one of these trees.

Abstract Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for any input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 min. Previous algorithms could only solve 16‐ or 17‐point point problems within the 30 min time bound. Problems involving 35 points can be solved, on average, within a day. Our experiments were run on uniformly distributed data on an integer grid.

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that under the Lp norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree for arbitrary Lp metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the Manhattan plane there exists an MST with maximum degree of at most 4, and for three-dimensional Manhattan space the maximum possible degree of a minimum degree MST is either 13 or 14.

The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing MRST heuristic to date is the Iterated 1-Steiner (I1S) method recently proposed by Kahng and Robins (see ibid., vol. 11, p. 893-902, 1992). In this paper, we develop a straightforward, efficient implementation of I1S, achieving a speedup factor of three orders of magnitude over previous implementations. We also give a parallel implementation that achieves near-linear speedup on multiple processors. Several performance-improving enhancements enable us to obtain Steiner trees with average cost within 0.25% of optimal, and our methods produce optimal solutions in up to 90% of the cases for typical nets. We generalize I1S and its variants to three dimensions, as well as to the case where all the pins lie on k parallel planes, which arises in, e.g., multilayer routing. Motivated by the goal of reducing the running times of our algorithms, we prove that any pointset in the Manhattan plane has a minimum spanning tree (MST) with maximum degree 4, and that in three-dimensional Manhattan space every pointset has an MST with maximum degree of 14 (the best previous upper bounds on the maximum MST degree in two and three dimensions are 6 and 26, respectively); these results are of independent theoretical interest and also settle an open problem in complexity theory.>

Presents a new strategy for performance-driven global routing. This strategy focuses on the creation of spanning trees whose properties are under the control of the designer. The authors use it to construct a spanning tree with simultaneous, provable performance guarantees on total length, single-source shortest path length, and bottleneck path length. For rectilinear problems on n terminals in the plane, such a tree can be constructed in O(n log n) time.>

Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for an input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 minutes. Previous algorithms could only solve 16 or 17-point problems within the 30-minute time bound.>

Given a set of points S, a t-spanner for S is a subgraph G of the complete Euclidean graph determined by S having the property that dG(x,y)/d(x,y) ≤ t for all x,y e S, x ≠ y, where dG(x, y) is the distance from point x is the euclidean distance from x to y. Dobkin, Friedman, and Supowit posed the problem of determining whether every planar point set S admits a t-spanner having maximum vertex degree 3 for some constant t. We show that for each k ≥ 2, there is a constant t(k) such that every point set in Rk admits a t(k)-spanner with vertex degree at most 4.

Given a set of input points, the rectilinear Steiner tree problem is to find a minimal-length tree consisting of vertical and horizontal line segments that connects the input points, where it is possible to add new points to minimize the length of the tree. The restricted Steiner tree problem in which all the input points lie on the boundary of a rectangle frequently occurs in VLSI physical design. Since the fastest published algorithm is cubic in the size of the point set, VLSI designers have been forced to use heuristic approximations to the length of the Steiner tree for this problem. A simple, practical, linear-time exact algorithm for finding the Steiner tree for points lying on the boundary of a rectangle which obviates the need for some heuristic algorithms in VLSI design is presented. The analysis of the algorithm is based on the use of a tie-breaking rule that should prove useful for other Steiner tree problems.>

Given n points in the plane and an integer k, the problem of selecting that pair of points that determines the line with the kth smallest or largest slope is considered. In the restricted case, where k is $O(n)$, line sweeping gives an optimal, $O(n\log n)$-time algorithm. For general k the parametric search technique of Megiddo is used to describe an $O(n(\log n)^2 )$-time algorithm. This is modified to produce a new, optimal $O(n\log n)$-time selection algorithm by incorporating an approximation idea.

The problem of finding the minimum-length rectilinear Steiner tree that connects a set of points on the boundary of a rectangle is considered. A linear time algorithm for this problem is presented. The algorithm was implemented in C and executed on a Sun3 workstation. Many examples were solved in a fraction of a second. An example with over 250 terminals took 6.5 s.>