HOME

TheInfoList



OR:

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 ...
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, therefore o ...
is replaced with the rectilinear distance. 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 electronic systems such as integrated circuits and printed circuit boards. The tools work together ...
. In VLSI circuits, wire routing 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 con ...
, 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 t ...
. 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 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
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 ...
which involves both input points and Steiner points as its vertices will require O(''n'' log ''n'') time, since it essentially accomplishes sorting 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 (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 rectilinear distance) 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)