On Bends and Distances of Paths Among Obstacles in Two-Layer Interconnection Model

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