Finding Geometric Medians with Location Privacy
Eyal Nussbaum, Michael Segal · 2020
We examine the problem of discovering the set P of points in a given topology which constitutes a k-median set for that topology, while maintaining location privacy. That is, there exists a set U of points in a d-dimensional topology for which a k-median set must be found by some algorithm A, without disclosing the location of points in U to the executor of A. We define a privacy preserving data model for a coordinate system we call a “Topology Descriptor Grid”, and show how it can be used to find the rectilinear 1-median of the system and a constant factor approximation for the Euclidean 1-median. Additionally, we achieve a constant factor approximation for the rectilinear 2-median of a grid topology.