earth mover's distance in 2D grid

CREATED: 200710180306

Can we compute the EMD in a n x m grid in time n x m when ground distance is the L1 metric?

Ling and Okada (2006) gave an O(N^2) algorithm for this problem in “An Efficient Earth Mover’s Distance Algorithm for Robust Histogram Comparison”