The Kantorovich metric for probability measures on the unit circle

CABRELLI, CARLOS A.; MOLTER, URSULA M.

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 1995 vol. 57 p. 345 - 361

0377-0427

In this paper we show that there exists an analytic expression for the Kantorovich distance between probabilitymeasures on the circle. Previously such an expression was only known for measures supported on the real line. In the casethat the measures are discrete, this formula enables us to show that the Kantorovich distance can be computed in lineartime. This is important for applications, in particular in pattern recognition where this distance is used for textureanalysis. As another application we see that the analytic expression found allows us to solve a Minimal MatchingProblem in linear time, for which so far only n log n algorithms were known.