Optimally solving a transportation problem using Voronoi diagrams
Optimally solving a transportation problem using Voronoi diagrams
复制标题
使用 Voronoi 图优化解决运输问题
DOI：
10.1016/j.comgeo.2013.05.005
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Günter Rote
中科院分区：
文献类型：
--
作者：
Darius Geiß;Rolf Klein;Rainer Penninger;Günter Rote
我们考虑著名的蒙日-坎托罗维奇运输问题的以下变体。令 S 为 Rd 中 n 个点位的集合。有界集合 C⊂Rdis 分布在站点 p∈S 之间，使得（i）每个 p 接收指定体积的子集 Cp，并且（ii）C 的所有点 z 与其各自站点 p 的平均距离最小化。在我们的模型中，体积通过测量 μ 进行量化，位置 p 和点 z 之间的距离由函数 dp(z) 给出。在对 C 和函数 dp(⋅) 相当自由的技术假设下，我们表明，基于配备了适当附加权重的函数 dp(⋅)，可以通过将 S 中的位置的 Voronoi 图与 C 相交来获得最小总成本的解决方案。此外，这个最佳划分是唯一的，最多可达零组测量。与经典交通理论的深度分析方法不同，我们的证明直接基于简单的几何论证。
We consider the following variant of the well-known Monge–Kantorovich transportation problem. Let S be a set of n point sites in Rd. A bounded set C⊂Rdis to be distributed among the sites p∈S such that (i) each p receives a subset Cpof prescribed volume and (ii) the average distance of all points z of C from their respective sites p is minimized. In our model, volume is quantified by a 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(⋅) equipped 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 simple geometric arguments.
点匹配的两种应用
DOI：
--
发表时间：
2009
期刊：
Computational geometry
影响因子：
--
作者：
G. Rote
通讯作者：
G. Rote
DOI：
10.1137/1.9781611973099.29
发表时间：
2012
期刊：
J. Comput. Geom.
影响因子：
--
作者：
R. Sharathkumar;P. Agarwal
通讯作者：
P. Agarwal