The rectilinear Steiner tree problem, minimum rectilinear Steiner tree problem (MRST), or rectilinear Steiner minimum tree problem (RSMT) is a variant of the geometric

Steiner tree problem In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a nu ...

in the plane, in which the

Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...

is replaced with the

rectilinear distance A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...

. The problem may be formally stated as follows: given ''n'' points in the plane, it is required to interconnect them all by a shortest network which consists only of vertical and horizontal line segments. It can be shown that such a network is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

whose vertices are the input points plus some extra points ( Steiner points). The problem arises in the physical design of

electronic design automation Electronic design automation (EDA), also referred to as electronic computer-aided design (ECAD), is a category of software tools for designing Electronics, electronic systems such as integrated circuits and printed circuit boards. The tools wo ...

. In

VLSI circuit Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...

wire routing In electronic design, wire routing, commonly called simply routing, is a step in the design of printed circuit boards (PCBs) and integrated circuits (ICs). It builds on a preceding step, called placement, which determines the location of each ...

is carried out by wires running only in vertical and horizontal directions, due to high

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of the task. Therefore wire length is the sum of the lengths of vertical and horizontal segments, and the distance between two pins of a net is actually the rectilinear distance ("Manhattan distance") between the corresponding geometric points in the design plane.Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"

Properties

It is known that the search for the RSMT may be restricted to the

Hanan grid In geometry, the Hanan grid of a finite set of points in the plane is obtained by constructing vertical and horizontal lines through each point in . The main motivation for studying the Hanan grid stems from the fact that it is known to conta ...

, constructed by drawing vertical and horizontal lines through each vertex.

Computational complexity

The RSMT is an

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

problem, and as with other NP-hard problems, common approaches to tackle it are approximate algorithms, heuristic algorithms, and separation of efficiently solvable special cases. An overview of the approaches to the problem may be found in the 1992 book by Hwang, Richards and Winter, ''The Steiner Tree Problem''.

Special cases

Single-trunk Steiner trees

The single-trunk Steiner tree is a tree that consists of a single horizontal segment and some vertical segments. A minimum single-trunk Steiner tree problem (MSTST) may be found in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. The idea is that STSTs for a given point set essentially have only one "degree of freedom", which is the position of the horizontal trunk. Further, it easy to see that if the Y-axis is split into segments by Y-coordinates of input points, then the length of a STST is constant within any such segment. Finally, it will be minimal if the trunk has the closest possible numbers of points below and above it. Therefore an optimal position of the trunk are defined by a

median In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...

of the set of Y-coordinates of the points, which may be found in linear time. Once the trunk is found, the vertical segments may be easily computed. Notice however that while the construction of the connecting net takes linear time, the construction of the

which involves both input points and Steiner points as its vertices will require O(''n'' log ''n'') time, since it essentially accomplishes

sorting Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. # ordering: arranging items in a sequence ordered by some criterion; # categorizing: grouping items with similar pro ...

of the X-coordinates of the input points (along the split of the trunk into the edges of the tree). A MSTST is fast to compute but is a poor approximation of the MRST. A better approximation, called the refined single trunk tree, may be found in O(''n'' log ''n'') time. It is optimal for point sets of sizes up to 4.

Approximations and heuristics

A number of algorithms exist which start from the

rectilinear minimum spanning tree In graph theory, the rectilinear minimum spanning tree (RMST) of a set of ''n'' points in the plane (or more generally, in ℝ''d'') is a minimum spanning tree of that set, where the weight of the edge between each pair of points is the rectiline ...

(RMST; the

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

in the plane with

) and try to decrease its length by introducing Steiner points. The RMST itself may be up to 1.5 times longer than MRST.F. K. Hwang. "On Steiner minimal trees with rectilinear distance." ''

SIAM Journal on Applied Mathematics The ''SIAM Journal on Applied Mathematics'' is a peer-reviewed academic journal in applied mathematics published by the Society for Industrial and Applied Mathematics (SIAM), with Paul A. Martin (Colorado School of Mines) as its editor-in-chief. I ...

'', 30:104–114, 1976.

References

{{DEFAULTSORT:Rectilinear Steiner Tree Geometric algorithms Geometric graphs NP-hard problems Trees (graph theory)