Optimally solving a transportation problem using Voronoi diagrams

DOI10.1007/978-3-642-32241-9_23zbMATH Open1282.49039arXiv1206.3057OpenAlexW3102109628MaRDI QIDQ2391547FDOQ2391547

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

Publication date: 31 July 2013

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

Abstract: We consider the following variant of the Monge-Kantorovich transportation problem. Let S be a finite set of point sites in d dimensions. A bounded set C in d-dimensional space is to be distributed among the sites p in S such that (i) each p receives a subset C_p of prescribed volume, and (ii) the average distance of all points of C from their respective sites p is minimized. In our model, volume is quantified by some measure, and the distance between a site p and a point z is given by a function d_p(z). Under quite liberal technical assumptions on C and on the functions d_p we show that a solution of minimum total cost can be obtained by intersecting with C the Voronoi diagram of the sites in S, based on the functions d_p with suitable additive weights. Moreover, this optimum partition is unique up to sets of measure zero. Unlike the deep analytic methods of classical transportation theory, our proof is based directly on geometric arguments.

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

Recommendations

• Optimally solving a transportation problem using Voronoi diagrams
• Reprint of: Optimally solving a transportation problem using Voronoi diagrams
• Numerical and analytical results for the transportation problem of Monge-Kantorovich
• The geometry of optimal transportation
• Faster algorithms for the geometric transportation problem

zbMATH Keywords

Wasserstein metricearth mover's distanceMonge-Kantorovich transportation problemVoronoi 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)

Cites Work

• The geometry of optimal transportation
• Optimal Transport
• Title not available (Why is that?)
• Minkowski-type theorems and least-squares clustering
• Geometry Helps in Matching
• Optimally solving a transportation problem using Voronoi diagrams
• Algorithms for the transportation problem in geometric settings

Cited In (10)

• Optimal 1-Wasserstein distance for WGANs
• Empirical optimal transport between different measures adapts to lower complexity
• Market areas in general equilibrium
• Optimally solving a transportation problem using Voronoi diagrams
• Graphical Interpretation of the Transportation Problem
• Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
• Dependence structure estimation using copula recursive trees
• Convex equipartitions via equivariant obstruction theory
• A multiplicatively-weighted Voronoi diagram approach to logistics districting
• Reprint of: Optimally solving a transportation problem using Voronoi diagrams

Uses Software

• EMD

This page was built for publication: Optimally solving a transportation problem using Voronoi diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391547)