An algorithm for exact rectilinear Steiner trees for switchbox with obstacles

Abstract

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(F1(k)n + F2(k)) time, where k is the number of obstacles inside the switchbox and F1 and F2 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.