## 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].
### 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.
Last update: June 15, 2012.