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.