Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
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.
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering