Using geometry to solve the transportation problem in the plane |
| |
Authors: | D S Atkinson P M Vaidya |
| |
Affiliation: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA |
| |
Abstract: | LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦= , andn=k+ . These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the 1 metric, the 2 metric, and the ![igr](/content/m31mh88853612753/xxlarge953.gif) metric. The running time for the 1 and ![igr](/content/m31mh88853612753/xxlarge953.gif) metrics can be improved to 0(n2(logn)3 logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195. |
| |
Keywords: | Transportation problem Scaling Voronoi diagrams Computational geometry |
本文献已被 SpringerLink 等数据库收录! |
|