2009/08/12 by Thomas Kaijser, Kaijser, Thomas
Computer Science · Engineering · #90C06 #90C08 #90C46 #90C90 #Automated Road and Building Extraction #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.0908.1649
openalex publication_date 2009/08/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.