Rectilinear Steiner Minimal Tree among obstacles

Rectilinear Steiner Minimal Tree (RSMT) is one of the key problems in VLSI/ULSI physical design. RSMT construction among obstacles is often used as an accurate estimation for wire length and delay throughout the process of routing, even placement and floorplanning. This paper studies RSMT problem among obstacles and presents an O(mn) 2-step heuristic for multi-terminal tree construction, where m is the number of obstacles and n is the number of terminals. This heuristic has been implemented and tested on MCNC benchmarks. The experimental results are encouraging.