Thick non-crossing paths and minimum-cost flows in polygonal domains

We study the problem of ?nding shortest non-crossing thick paths in a polygonal domain, where a thick path is the Min-kowski sum of a usual (zero-thickness, or thin) path and a disk. Given K pairs of terminals on the boundary of a sim- ple n-gon, we compute in O(n + K) time a representation of the set of K shortest non-crossing thick paths joining the terminal pairs; using the representation, any particular path can be output in time proportional to its complexity. We compute K shortest thick non-crossing paths in a polygon with h holes in O (n+k) poly(n;K) time, us-ing an e?cient method to compute any one of the K thick paths if the "threadings" of all paths amidst the holes are speci?ed. We show that if h is not constant, the problem is NP-hard; we also show the hardness of approximation. We give a pseudopolynomial-time algorithm for some rectilinear versions of the problem. We apply our thick paths algorithms to obtain the ?rst algorithmic results for the minimum-cost continuous ow problem | an extension of the standard discrete minimum-cost network ow problem to continuous domains. The re-sults are based on showing a continuous analog of the Net-work Flow Decomposition Theorem.