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

Optimally solving a transportation problem using Voronoi diagrams

Computational Geometry, Theory and Applications 46 (2013), 1009–1016, special issue for the 28th European Workshop on Computational Geometry (EuroCG'12). doi:10.1016/j.comgeo.2013.05.005, arXiv:1206.3057 [math.MG].


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 Cp 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 dp(z). Under quite liberal technical assumptions on C and on the functions dp 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 dp 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.

  pdf file (gzipped)
other papers about this subject
Last update: June 15, 2012.