Title: The Smallest Pair of Non-Crossing Paths in a Rectilinear Polygon

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

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 the 
  Grant CCR-9309743, and by the Office of Naval Research under 
  the Grants No. N00014-93-1-0272 and No. N00014-95-1-1007.

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

Abstract:

Smallest rectilinear paths are rectilinear paths with a minimum number 
of bends and with a minimum length simultaneously. In this paper given
two pairs of terminals within a rectilinear polygon, we derive an 
algorithm to find a pair of  non-crossing rectilinear paths within 
the polygon such that the total number of bends and the total length 
are both minimized. Although a smallest rectilinear path between 
two terminals in a rectilinear polygon always exists, we show that
such a smallest pair may not exist for some problem instances.
In that case the algorithm presented will either find  among all 
non-crossing paths with a minimum total number of bends, a pair 
whose total length is the shortest, or find among all non-crossing 
paths with a minimum total length, a pair whose total number of 
bends is minimized. We provide a simple linear time and space 
algorithm based on the fact that there are only a limited number of 
configurations of such a solution pair.

IEEE Transactions on Computers, (46,8) August 1997, 930-941.