Summary
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).[1]
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 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.[1]
Properties edit
In 1966 Maurice Hanan demonstrated that the search for the RSMT may be restricted to the grid constructed by drawing vertical and horizontal lines through each vertex, now known as the Hanan grid.[2]
Computational complexity edit
The RSMT is an NP-hard 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.[3]
Special cases edit
Single-trunk Steiner trees edit
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 (MSTST) may be found in O(n log n) time. However simply finding all its edges requires 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 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 uses both input points and Steiner points as its vertices will require O(n log n) time, since the required connection essentially delivers sorting of the X-coordinates of the input points (along the split of the trunk into the edges of the tree).[4]
A MSTST is fast to compute but is a poor approximation of the MRST. A better approximation, called the refined single trunk tree (RST-T), may be found in O(n log n) time. The idea is to replace some connections to the trunk with connections to previous connections if this is advantageous, following a simple heuristic. It is optimal for point sets of sizes up to 4.[5]
Approximations and heuristics edit
A number of algorithms exist which start from the rectilinear minimum spanning tree (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.[6]
References edit
- ^ a b Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"
- ^ M. Hanan, On Steiner’s problem with rectilinear distance, J. SIAM Appl. Math. 14 (1966), 255 - 265.
- ^ F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem. Elsevier, North-Holland, 1992, ISBN 0-444-89098-X (hardbound) (Annals of Discrete Mathematics, vol. 53).
- ^ J. Soukup. "Circuit Layout". Proceedings of the IEEE, 69:1281–1304, October 1981
- ^ H. Chen, C. Qiao, F. Zhou, and C.-K. Cheng. "Refined single trunk tree: A rectilinear Steiner tree generator for interconnect prediction". In: Proc. ACM Intl. Workshop on System Level Interconnect Prediction, 2002, pp.85–89.
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal on Applied Mathematics, 30:104–114, 1976.