Title: Finding Rectilinear Paths among Obstacles in a Two-Layer
Interconnection Model
D.T. Lee*
Department of Electrical and Computer Engineering
Northwestern University
Evanston, IL, 60208 USA
dtlee@ece.nwu.edu
* Supported in part by the National Science Foundation
under grants CCR-8901815 and CCR-9309743
C. D. Yang
Avant! Corporation
46871 Bayside Parkway
Fremont, CA 94538
yangcd@avanticorp.com
C. K. Wong
Department of Computer Science
Chinese University of Hong Kong
Shatin, New Territories, Hong Kong
wongck@cs.cuhk.hk
Abstract:
Finding the best rectilinear path with respect to the bends and the
lengths of paths connecting two given points in the presence of
rectilinear obstacles in a two-layer model is studied in this paper.
In this model, rectilinear obstacles on each layer are specified
separately, and the orientation of routing in each layer is fixed.
An algorithm is presented to transform any problem instance in the
two-layer model to one in a one-layer model, so that almost all
algorithms for finding rectilinear paths among obstacles in the plane
can be applied.
The transformation algorithm runs in $O(e\log e)$ time where $e$ is
the number of edges on obstacles lying on both layers. A direct
graph-theoretic approach to finding a shortest path in the two-layer
model, which is easier to implement is also presented. The algorithm
runs in $O(e\log^2e)$ time.
Keywords: Rectilinear shortest path, grid graph, minimum link path,
VLSI routing.
Int' J. Computational Geometry & Applications, (7,6) Dec. 1997, pp. 581-598.