Generation of optimal obstacle-avoiding rectilinear Steiner minimum tree

In this paper, we present an efficient method to solve the obstacle-avoiding rectilinear Steiner tree problem optimally. Our work is developed based on the GeoSteiner approach, modified and extended to allow rectilinear blockages in the routing region. We extended the proofs on the possible topologies of full Steiner tree (FST) to allow blockages, where FST is the basic concept used in GeoSteiner. We can now handle hundreds of pins with multiple blockages, generating an optimal solution in a reasonable amount of time. This work serves as a pioneer in providing an optimal solution to this difficult problem.