On maximum flows in polyhedral domains

摘要

We introduce a new class of problems concerned with the computation of maximum flows through two-dimensional polyhedral domains. Given a polyhedral space (e.g., a simple polygon with holes), we want to find the maximum “flow” from a source edge to a sink edge. Flow is defined to be a divergence-free vector field on the interior of the domain, and capacity constraints are specified by giving the maximum magnitude of the flow vector at any point. The problem is the natural extension to the continuous domain of the discrete problem of finding maximum flows through a capacitated network. For this problem, Strang proved that max flow equals min cut; we address the problem of constructing min cuts and max flows. We give polynomial-time algorithms for maximum flow from a source edge to a sink edge through a simple polygon with uniform capacity constraint (with or without holes), maximum flow through a simple polygon from many sources to many sinks, and maximum flow through weighted polygonal regions. Central to our methodology is the intimate connection between the max-flow problem and its dual, the min-cut problem. We show how the continuous Dijkstra paradigm of solving shortest paths problems corresponds to a continuous version of the uppermost path algorithm for computation of maximum flow in a planar network.