A minimum separation algorithm for river routing with bounded number of jogs

Abstract

The single-layer rectilinear river routing model with no restriction on the number of jogs per wire is considered. In particular, the author studies the model in which there is a fixed constant upper bound J on the number of jogs each wire can have. The author proposes an optimal O(n) time algorithm for the feasibility problem. This leads to an O(n log n) time algorithm for the minimum separation problem. Both algorithms take O(n) space are quite practical. This is a significant improvement over T.C. Tuan and S.L. Hakimi's (1987) minimum separation algorithm, which is designed for J=2 and takes O(n/sup 3/) time and O(n/sup 2/) space.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>