Rectilinear Steiner tree
Encyclopedia
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 the plane, in which the Euclidean distance
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
whose vertices are the input points plus some extra points (Steiner points).
The problem arises in the physical design
of electronic design automation
. In VLSI circuits, wire routing is carried out by wires running only in vertical and horizontal directions, due to high computational complexity
of the task. Therefore wire length is the sum of the lengths of verticall 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.
It is known that the search for the RMST may be restricted to the Hanan grid
, constructed by drawing vertical and horizontal lines through each vertex.
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.
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
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.
(RMST; the minimum spanning tree
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.
Euclidean distance
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
whose vertices are the input points plus some extra points (Steiner points).
The problem arises in the physical design
Physical design (electronics)
In integrated circuit design, physical design is a step in the standard design cycle which follows after the circuit design. At this step, circuit representations of the components of the design are converted into geometric representations of shapes which, when manufactured in the corresponding...
of electronic design automation
Electronic design automation
Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
. In VLSI circuits, wire routing is carried out by wires running only in vertical and horizontal directions, due to high computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of the task. Therefore wire length is the sum of the lengths of verticall 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.
Properties
Hanan grid
In geometry, the Hanan grid H of a finite set S of points in the plane is obtained by constructing vertical and horizontal lines through each point in S....
, constructed by drawing vertical and horizontal lines through each vertex.
Computational complexity
The RSMT is an NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
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.
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.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
Median
In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
of the set of Y-coordinates of the points, which may be found in linear time
Selection algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list . This includes the cases of finding the minimum, maximum, and median elements. There are O, worst-case linear time, selection algorithms...
. 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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
which involves both input points and Steiner points as its vertices will require O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n) time, since it essentially accomplishes sorting
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
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
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(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 treeRectilinear minimum spanning tree
In graph theory, the rectilinear minimum spanning tree of a set of n points in the plane is a minimum spanning tree of that set, where the weight of the edge between each pair of points is the rectilinear distance between those two points.-Electronic design:The problem commonly arises in physical...
(RMST; the minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
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.