Rectilinear Steiner Tree Construction

Summary
Construction of rectilinear Steiner minimum tree (RSMT) is an important problem in VLSI physical design. It is useful for the detailed and global routing steps, and is important for congestion, wire length and timing estimations during the floorplanning or placement step. This classical problem has long been shown to be NP-complete and has attracted a lot of attentions in research. The original RSMT problem assumes no obstacles in the routing region. In today's VLSI designs, there can be many routing blockages however, like macro cells, IP blocks and pre-routed nets. Therefore, the RSMT problem with blockages, called obstacle avoiding RSMT (OARSMT), has become an important problem in practice and is an interesting problem theoretically.