Title: Rectilinear Paths among Rectilinear Obstacles*

*Supported in part by the National Science Foundation under
Grants CCR-8901815 and CCR-9309743.

D.T. Lee 
Department of Electrical and Computer Engineering 
Northwestern University
Evanston, IL 60208
dtlee@ece.nwu.edu

C. D. Yang
Avant! Corporation
46871 Bayside Parkway
Fremont, CA  94538
yangcd@avanticorp.com

and 

C. K. Wong*
Department of Computer Science
Chinese University of Hong Kong
Shatin, New Territories, Hong Kong
wongck@cs.cuhk.hk

*On leave from IBM T. J. Watson Research Center
P.O. Box 218
Yorktown Heights, NY 10598

Abstract: 

Given a set of obstacles and two distinguished points in the plane
the problem of finding a collision free path subject to a certain
optimization function is a fundamental problem that arises in many
fields, such as motion planning in robotics, wire routing in VLSI
and logistics in operations research.  In this survey we emphasize 
its applications to VLSI design and limit ourselves to the rectilinear 
domain in which the goal path to be computed and the underlying 
obstacles are all rectilinearly oriented, i.e., the segments are 
either horizontal or vertical.  We consider different routing 
environments, and various optimization criteria pertaining to VLSI 
design, and provide a survey of results that have been developed
in the past, present current results and give open problems for future 
research.

Discrete Applied Math., 70 (1996), 185-215.