liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Optimal Geometric Flows via Dual Programs
Courant Institute NYU.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
Google, Inc. Zurich.
2014 (English)In: Annual Symposium on Computational Geometry, 2014, 100-109 p.Conference paper (Refereed)Text
Abstract [en]

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.

Place, publisher, year, edition, pages
2014. 100-109 p.
National Category
Fluid Mechanics and Acoustics
URN: urn:nbn:se:liu:diva-128022ISBN: 978-1-4503-2594-3OAI: diva2:928739
SoCG 2014
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-26

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Fluid Mechanics and Acoustics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link