Augmented Line Segment Based Algorithm for Constructing Rectilinear Steiner Minimum Tree

摘要

A new algorithm has been proposed to construct the Rectilinear Steiner Minimum Tree by incrementally increasing the length of four line segments drawn at each point. An edge is added to the tree when two line segments intersect. A new strategy has been used while performing a decision in selecting one of the two rectilinear edges. The algorithm removes the problem of local error, a wire length error that occurs due to the previous decision in selecting one of the two rectilinear edges and generates near-optimal Rectilinear Steiner Minimum Tree. The run time of the above algorithm is dependent on the maximum length of the edge in the constructed rectilinear tree. RSMT is widely used in the global routing phase of VLSI design and reducing the length of RSMT results in wire length reduction.