Considering potentials in the dual of a planar network has proved to be a powerful tool for computing planar maximum flows. In this paper we explore the use of potentials for giving algorithmic and combinatorial results on continuous flows in geometric domains -- a (far going) generalization of discrete flows in unit-capacity planar networks.
A continuous flow in a polygonal domain is a divergence-free vector field whose magnitude at every point is bounded by a given constant -- the domain's permeability. The flow enters the domain through a source edge on the outer boundary of the domain, and leaves through a sink edge on the boundary. The value of the flow is the total flow amount that comes in through the source (the same amount comes out of the sink, due to the vanishing divergence). The cost of the flow is the total length of its streamlines. The flow is called monotone if its streamlines are x-monotone curves.
Our main result is an algorithm to find (an arbitrarily close approximation to) the minimum-cost monotone flow in a polygonal domain, by formulating the problem as a convex program with an interesting choice of variables: one variable per hole in the domain. Our approach is based on the following flow of ideas: flow is the gradient of a potential function; a potential function can be extended from free space to holes so that it is constant over each hole; instead of the potential function (a value per point in the domain) we can thus speak of a potential vector (a value per hole); a potential uniquely (up to homotopic equivalence) defines "thick" paths in the domain; the paths define a flow. We show that the flow cost is convex in the potential; this allows us to employ the ellipsoid method to find the mincost flow, using holes potentials as variables. At each ellipsoid iteration the separation oracle is implemented by feasibility checks in the "critical graph" of the domain -- as we prove, the graph defines linear constraints on the potentials.
Using potentials and critical graphs we also prove MaxFlow/MinCut theorems for geometric flows -- both for monotone and for general ones. Formulating and proving the monotone version is a new result. The MaxFlow/MinCut theorem for non-monotone flows has been proved earlier by two different methods; the potentials technique provides a third proof.
2014. 100-109 p.