Improving the primal-dual algorithm for the transportation problem in the plane

Mathematics – Optimization and Control

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-370275

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.