  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.
