Optimally solving a transportation problem using Voronoi diagrams

DOI10.1016/j.comgeo.2013.05.005zbMath1282.49039arXiv1206.3057OpenAlexW3102109628MaRDI QIDQ2391547

Rainer Penninger, Darius Geiß, Günter Rote, Rolf Klein

Publication date: 31 July 2013

Published in: Lecture Notes in Computer Science, Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.3057

zbMATH Keywords

Wasserstein metricMonge-Kantorovich transportation problemearth mover's distanceVoronoi diagram with additive weights

Mathematics Subject Classification ID

Variational problems in a geometric measure-theoretic setting (49Q20) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Related Items

Optimally solving a transportation problem using Voronoi diagrams, Reprint of: Optimally solving a transportation problem using Voronoi diagrams, Market areas in general equilibrium, Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case, Convex equipartitions via equivariant obstruction theory, Dependence structure estimation using copula recursive trees

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• The geometry of optimal transportation
• Minkowski-type theorems and least-squares clustering
• Optimally solving a transportation problem using Voronoi diagrams
• Geometry Helps in Matching
• Optimal Transport