View source for Rectilinear Steiner tree

{{Short description|Variant of the Steiner tree problem in geometry and combinatorics}}
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 (graph theory)|tree]] whose vertices are the input points plus some extra points ([[Steiner tree problem|Steiner points]]).<ref name=sher/>

The problem arises in the [[Engineering:Physical design (electronics)|physical design]] of [[Engineering:Electronic design automation|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 theory|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.<ref name=sher>Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"</ref>

==Properties==
[[File:Hanan5.svg|thumb|Hanan grid for a 5-vertex case]]
It is known that the search for the RSMT may be restricted to the [[Hanan grid]], constructed by drawing vertical and horizontal lines  through each vertex.<ref>M. Hanan, On Steiner’s problem with rectilinear distance, J. SIAM Appl. Math. 14 (1966), 255 - 265.</ref>

==Computational complexity==
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''.<ref>F.K. Hwang, D.S. Richards, P. Winter, ''The Steiner Tree Problem''. [[Company:Elsevier|Elsevier]], North-Holland, 1992, {{isbn|0-444-89098-X}} (hardbound) (Annals of Discrete Mathematics, vol. 53).</ref>

===Special cases===
====Single-trunk Steiner trees====
[[File:1trunkStT.png|thumb|right|200px|A MSTST]]
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]] 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 (graph theory)|tree]] which involves both input points and Steiner points as its vertices will require [[Big O notation|O]](''n''&nbsp;log&nbsp;''n'') time, since  it essentially accomplishes [[Sorting algorithm|sorting]] of the X-coordinates of the input points (along the split of the trunk into the edges of the tree).<ref>J. Soukup. "Circuit Layout". ''[[Proceedings of the IEEE]]'', 69:1281–1304, October 1981</ref>

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 [[Big O notation|O]](''n''&nbsp;log&nbsp;''n'') time. It is optimal for point sets of sizes up to 4.<ref>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.</ref>

===Approximations and heuristics===
A number of algorithms exist which start from the [[Rectilinear minimum spanning tree|rectilinear minimum spanning tree]] (RMST; the [[Minimum spanning tree|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.<ref>F. K. Hwang. "On Steiner minimal trees with rectilinear
distance." ''[[SIAM Journal on Applied Mathematics]]'', 30:104–114, 1976.</ref>

==References==
{{Reflist}}

{{DEFAULTSORT:Rectilinear Steiner Tree}}
[[Category:Geometric algorithms]]
[[Category:Geometric graphs]]
[[Category:Trees (graph theory)]]

{{Sourceattribution|Rectilinear Steiner tree}}