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.?
