IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications

An Algorithm for Exact Rectilinear Steiner Trees for Switchbox with Obstacles

View publication


The switchbox rectilinear Steiner tree problem is to construct an optimal rectilinear Steiner tree interconnecting n terminals on the perimeter of a switchbox without crossing any obstacles inside the switchbox. However, intersecting boundaries of obstacles is allowed. We present an algorithm that computes an optimal switchbox rectilinear Steiner tree in O(F<inf>1</inf>(k)n + F<inf>2</inf>(k)) time, where k is the number of obstacles inside the switchbox and F<inf>1</inf> and F<inf>2</inf> are exponential functions of k. For any constant k, the proposed algorithm runs in O(n) time. As an immediate extension, we can generate m Steiner trees in O(mn) time, and among them, select the best one. © 1992 IEEE