About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE TC
Paper
On Bends and Distances of Paths Among Obstacles in Two-Layer Interconnection Model
Abstract
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