We examine well known facility location problems under the privacy challenges posed by big data environments. For a given set of n points \(U\in \mathbb {R}^d\) , previous works have introduced the “Topology Descriptor Grid” (TDG) [13, 14], a privacy-preserving framework under which some approximate solutions are possible for a variety of clustering problems. In this paper, we introduce the Equidistant “Location Estimation using Concentric Circles” (LECC) framework in \(\mathbb {R}^2\) , which obfuscates exact point locations while preserving their relative distances to a predetermined point. We show, under this new framework, how to obtain \(2+\mathcal {O}(1/n)\) -approximate solutions for the 1-center, 1-median, 1-mean, and k-centrum problems, and \(\mathcal {O}(k),\mathcal {O}(k),\mathcal {O}(k^2)\) approximations for the k-center, k-median and k-means problems, respectively. For the TDG framework we provide a \((\sqrt{d},k^{d-1}),(d,k^{d-1})\) , and \((d^2,k^{d-1})\) approximations for the k-center, k-median, and k-means problems, respectively.