کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327398 | 681023 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimally solving a transportation problem using Voronoi diagrams
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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âRd is to be distributed among the sites pâS such that (i) each p receives a subset Cp of 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 8, October 2013, Pages 1009-1016
Journal: Computational Geometry - Volume 46, Issue 8, October 2013, Pages 1009-1016
نویسندگان
Darius GeiÃ, Rolf Klein, Rainer Penninger, Günter Rote,