Title :
Smallest paths in simple rectilinear polygons
Author :
McDonald, Kenneth M. ; Peters, Joseph G.
Author_Institution :
Sch. of Comput. Sci., Simon Fraser Univ., Burnaby, BC, Canada
fDate :
7/1/1992 12:00:00 AM
Abstract :
A smallest path between two points is a rectilinear path that simultaneously minimizes distance and the number of horizontal and vertical line segments in the path. Potential applications of smallest rectilinear paths include the simultaneous minimization of vias and wire lengths in two-layer chips, optimization of routes for robots, and the planning of traffic routes in cities with gridlike road systems. The existence of a smallest path between any pair of points in a simple rectilinear polygon with n boundary segments is proven and an optimal O(n) time sequential algorithm for finding the smallest paths is presented. An O(log n) parallel algorithm for an n processor CREW PRAM is described
Keywords :
circuit layout CAD; minimisation; parallel algorithms; CREW PRAM; city traffic routes planning; gridlike road systems; horizontal/vertical line segments minimization; minimizes distance; n processor; parallel algorithm; rectilinear path; rectilinear polygons; robot routes optimization; simultaneous minimization; smallest rectilinear paths; two-layer chips; vias minimization; wire length minimization; Cities and towns; Length measurement; Parallel algorithms; Path planning; Phase change random access memory; Roads; Robot sensing systems; Robotics and automation; Very large scale integration; Wires;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
