J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
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(F1(k)n + F2(k)) time, where k is the number of obstacles inside the channel and F1 and F2 are exponential functions of k. For any constant k the proposed algorithm runs in O(n) time. Copyright © 1991 John Wiley & Sons, Ltd.
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
Heng Cao, Haifeng Xi, et al.
WSC 2003
George Markowsky
J. Math. Anal. Appl.