River Routing Every Which Way, But Loose
Richard Cole, Andrew F. Siegel · 1984
A solution to the 'Detailed Routing given a Homotopy' (DRH) problem is given in O(n + mlogm + D(m)) operations. The solution uses n + mlogm homotopy queries that are elementary; they are answerable based solely on "local properties" of modules, terminals, and wire connections. In addition, we need O(m) more complex queries, which are represented in the D(m) term. These queries must account for the total number of crossin s occurringfor selected test segments.