Mathematics – Optimization and Control
Scientific paper
2009-08-12
Mathematics
Optimization and Control
1) This paper was written in 1999. 2) I have added the term "earth mover's distance" to the list of keywords. 3) I have added
Scientific paper
The transportation problem in the plane - how to move a set of objects from one set of points to another set of points in the cheapest way - is a very old problem going back several hundreds of years. In recent years the solution of the problem has found applications in the analysis of digital images when searching for similarities and discrepancies between images. The main drawback, however, is the long computation time for finding the solution. In this paper we present some new results by which the time for solving the transportation problem in the plane can be reduced substantially. As cost-function we choose a distance-function between points in the plane. We consider both the case when the distance-function is equal to the ordinary Euclidean distance, as well as the case when the distance-function is equal to the square of the Euclidean distance. This latter distance-function has the advantage that it is integer-valued if the coordinates of the points in the plane are integers.
No associations
LandOfFree
Improving the primal-dual algorithm for the transportation problem in the plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improving the primal-dual algorithm for the transportation problem in the plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improving the primal-dual algorithm for the transportation problem in the plane will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-370275