2 added 27 characters in body

How much have you looked into the theory of optimal transport? It's very popular for image warping/registration.

There's codes available to compute the $l1$-optimal transport distance (also referred to as "Earth mover's distance") here: http://ai.stanford.edu/~rubner/emd/default.htm and here: http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/

The $l2$ optimal mass transport problem is quite difficult but can be solved: http://www.springerlink.com/index/40PGJBKDC9V0UH94.pdf

Once it's possible to compute the cost to get between two distributions of points I guess you'll have to optimize to see which distribution is closest to the one you have. Maybe something like: $$\min_\rho d(\rho_0, \rho)\;subject\;to\;\rho \leq c, \rho \geq 0,\int \rho = 1$$ where $\rho$ is a probability distribution describing the density of points and $c$ is your threshold. Maybe you can do this with a Lagrange multiplier and gradient descent.?

1

How much have you looked into the theory of optimal transport? It's very popular for image warping/registration.

There's codes available to compute the $l1$-optimal transport distance (also referred to as "Earth mover's distance") here: http://ai.stanford.edu/~rubner/emd/default.htm and here: http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/

The $l2$ optimal mass transport problem is quite difficult but can be solved: http://www.springerlink.com/index/40PGJBKDC9V0UH94.pdf

Once it's possible to compute the cost to get between two distributions of points I guess you'll have to optimize to see which distribution is closest to the one you have. Maybe something like: $$\min_\rho d(\rho_0, \rho)\;subject\;to\;\rho \leq c$$ where $\rho$ is a probability distribution describing the density of points and $c$ is your threshold. Maybe you can do this with a Lagrange multiplier and gradient descent.