Oswin Aichholzer, Franz Aurenhammer, et al.
International Journal of Computational Geometry and Applications
In this paper, we consider problems of finding assorted rectilinear paths among rectilinear obstacles in two-layer interconnection model according to the number of bends and the 1-layer distance (y-distance). Using a horizontal wavefront approach, optimal θ(eloge) time algorithms are presented to find the shortest path and the minimum-bend path using linear space, and to find the shortest minimum-bend path and the minimum-bend shortest path using O(e log e) space, where e is the number of obstacle edges. By the same approach, we also derive an algorithm for finding a shortest two-layer distance (xy- distance) minimum-bend path in optimal O(e log e) time using O(e log e) space. © 1994 IEEE
Oswin Aichholzer, Franz Aurenhammer, et al.
International Journal of Computational Geometry and Applications
A.C. McKellar, C.K. Wong
Journal of the ACM
Jingsheng Cong, Andrew B. Kahng, et al.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Guochuan Zhang, Xiaoqiang Cai, et al.
IIE Transactions