Discrete optimal transport: complexity, geometry and applications

DOI10.1007/s00454-016-9757-7zbMath1339.49040OpenAlexW2281783425MaRDI QIDQ262303

Edouard Oudet, Quentin Mérigot

Publication date: 29 March 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-016-9757-7

zbMATH Keywords

algorithmregularityGaussian measureBrunn-Minkowski inequalityAlexandrov problemdiscrete optimal transportdual linear program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical methods involving duality (49M29) Linear programming (90C05) Variational problems in a geometric measure-theoretic setting (49Q20) Regularity of solutions in optimal control (49N60) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Combinatorial complexity of geometric structures (52C45)

Related Items

Error Bounds for Discretized Optimal Transport and Its Reliable Efficient Numerical Solution ⋮ Optimal Transport via a Monge--Ampère Optimization Problem ⋮ Quantization and clustering on Riemannian manifolds with an application to air traffic analysis ⋮ An algorithm to approximate the optimal expected inner product of two vectors with given marginals

Cites Work

• Unnamed Item
• Prescription of Gauss curvature using optimal mass transport
• Nonsmooth optimization via quasi-Newton methods
• Weak solutions of one inverse problem in geometric optics
• Convexity of injectivity domains on the ellipsoid of revolution: the oblate case
• A class of Cartesian grid embedded boundary algorithms for incompressible flow with time-varying complex geometries
• Necessary and sufficient conditions for continuity of optimal transport maps on Riemannian manifolds
• Towards auction algorithms for large dense assignment problems
• On the numerical solution of the equation \(\frac{\partial ^ 2z\partial ^ 2z}{\partial x^ 2\partial y^ 2}-(\frac{\partial ^ 2z}{\partial x\partial y})^ 2=f\) and its discretizations. I
• Dual coordinate step methods for linear network flow problems
• Minkowski-type theorems and least-squares clustering
• Numerical solution of the Monge--Ampère equation by a Newton's algorithm
• Optimum quantization and its applications
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• Embedding \(\mathbb S^n\) into \(\mathbb R^{n+1}\) with given integral Gauss curvature and optimal mass transport on \(\mathbb S^n\)
• Approximation by finitely supported measures
• Assignment Problems
• Least squares quantization in PCM
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• On the Subdifferentiability of Convex Functions
• Optimal Transport