RECTILINEAR PATHS AMONG RECTILINEAR OBSTACLES

Given a set of obstacles and two distinguished points in the plane the problem of finding a collision-free path subject to a certain optimiz ation function is a fundamental problem that arises in many fields, su ch as motion planning in robotics, wire routing in VLSI and logistics in operations research. In this survey we emphasize its applications t o VLSI design and limit ourselves to the rectilinear domain in which t he goal path to be computed and the underlying obstacles are all recti linearly oriented, i.e., the segments are either horizontal or vertica l. We consider different routing environments, and various optimizatio n 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.