An optimal algorithm for rectilinear steiner trees for channels with obstacles

The channel rectilinear Steiner tree problem is to construct an optimal rectilinear Steiner tree interconnecting n terminals on the upper shore and the lower shore of a channel without crossing any obstacles inside the channel. However, intersecting boundaries of obstacles is allowed. We present an algorithm that computes an optimal channel rectilinear Steiner tree in O(F₁(k)n + F₂(k)) time, where k is the number of obstacles inside the channel and F₁ and F₂ are exponential functions of k. For any constant k the proposed algorithm runs in O(n) time.