THE SMALLEST PAIR OF NONCROSSING PATHS IN A RECTILINEAR POLYGON

Smallest rectilinear paths are rectilinear paths with a minimum number of bends and with a minimum length simultaneously. In this paper, giv en two pairs of terminals within a rectilinear polygon, we derive an a lgorithm to find a pair of noncrossing rectilinear paths within the po lygon such that the total number of bends and the total length are bot h minimized. Although a smallest rectilinear path between two terminal s in a rectilinear polygon always exists, we show that such a smallest pair may not exist for some problem instances. In that case, the algo rithm presented will find, among all noncrossing paths with a minimum total number of bends, a pair whose total length is the shortest, or f ind, among all noncrossing paths with a minimum total length, a pair w hose total number of bends is minimized. We provide a simple linear ti me and space algorithm based on the fact that there are only a limited number of configurations of such a solution pair.