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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, p. 100-109Conference paper, Published paper (Refereed)
Resource type
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. p. 100-109
National Category
Fluid Mechanics and Acoustics
Identifiers
URN: urn:nbn:se:liu:diva-128022ISBN: 978-1-4503-2594-3 (print)OAI: oai:DiVA.org:liu-128022DiVA, id: diva2:928739
Conference
SoCG 2014
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-26

Open Access in DiVA

No full text in DiVA

Authority records

Polishchuk, Valentin

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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf