Geomasking through Perturbation, or Counting Points in Circles

Universitat Politècnica de Catalunya

Motivated by a problem in privacy protection, in which $n$ points are randomly perturbed by at most a distance $r$, we study a the following problem: Given $n$ points and $m$ circles in the plane, what is the maximum $r$ such that the number of points included in each circle does not change? We also consider a more general question, where we allow the number of points included in each circle to change by a certain factor. We give several algorithms for the problems, and analyze what parameters of the input influence their running times in practice.