  Consider the problem of optimally matching two measures on the circle, or
equivalently two periodic measures on the real line, and suppose the cost of
matching two points satisfies the Monge condition. We introduce a notion of
locally optimal transport plan, motivated by the weak KAM (Aubry-Mather)
theory, and show that all locally optimal transport plans are conjugate to
shifts and that the cost of a locally optimal transport plan is a convex
function of a shift parameter. This theory is applied to a transportation
problem arising in image processing: for two sets of point masses on the
circle, both of which have the same total mass, find an optimal transport plan
with respect to a given cost function satisfying the Monge condition. In the
circular case the sorting strategy fails to provide a unique candidate solution
and a naive approach requires a quadratic number of operations. For the case of
$N$ real-valued point masses we present an O(N |log epsilon|) algorithm that
approximates the optimal cost within epsilon; when all masses are integer
multiples of 1/M, the algorithm gives an exact solution in O(N log M)
operations.
