Smallest paths in simple rectilinear polygons

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>