Geomasking through Perturbation, or Counting Points in Circles

Motivated by a technique in privacy protection, in which n points are randomly perturbed by at most a distance r, we study 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 discuss several algorithms for the problems, analyze what parameters of the input influence their running times, and consider a special case where the circles are aligned on a grid, which has important applications.

keywords: Computational Geometry, Data Imprecision, UDG

Workshop or Poster (weakly reviewed)

Jun Luo, Maarten Löffler, Rodrigo I. Silveira
Geomasking through Perturbation, or Counting Points in Circles
Proc. 33rd European Workshop on Computational Geometry
209–212, 2017

back to list