A Multiscale Approach to Optimal Transport

Simple item page
dc.contributor.authorMérigot, Quentinen_US
dc.contributor.editorMario Botsch and Scott Schaeferen_US
dc.date.accessioned2015-02-27T15:03:39Z
dc.date.available2015-02-27T15:03:39Z
dc.date.issued2011en_US
dc.description.abstractIn this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth-mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.identifier.doi10.1111/j.1467-8659.2011.02032.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2011.02032.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]en_US
dc.subjectComputational Geometry and Object Modelingen_US
dc.subjectGeometric algorithmsen_US
dc.subjectlanguagesen_US
dc.subjectand systemsen_US
dc.titleA Multiscale Approach to Optimal Transporten_US
Files
Collections
30-Issue 5
SGP11: Eurographics Symposium on Geometry Processing