Private Approximations of a Convex Hull in Low Dimensions
This work addresses privacy-preserving computational geometry for data analysts, offering incremental improvements by adapting existing kernel methods to private settings.
The paper tackles the problem of estimating geometric features like convex hull volume under differential privacy constraints, introducing the first differentially private algorithms for such tasks with bi-criteria approximations that provide bounds on the error.
We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull, min-bounding box, min-enclosing ball etc. Our work relies heavily on the notion of \emph{Tukey-depth}. Instead of (non-privately) approximating the convex-hull of the given set of points $P$, our algorithms approximate the geometric features of the $κ$-Tukey region induced by $P$ (all points of Tukey-depth $κ$ or greater). Moreover, our approximations are all bi-criteria: for any geometric feature $μ$ our $(α,Δ)$-approximation is a value "sandwiched" between $(1-α)μ(D_P(κ))$ and $(1+α)μ(D_P(κ-Δ))$. Our work is aimed at producing a \emph{$(α,Δ)$-kernel of $D_P(κ)$}, namely a set $\mathcal{S}$ such that (after a shift) it holds that $(1-α)D_P(κ)\subset \mathsf{CH}(\mathcal{S}) \subset (1+α)D_P(κ-Δ)$. We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by Agarwal et al~[2004], \emph{fails} to give a kernel, and so we result to subtler notions of approximations of projections that do yield a kernel. First, we give differentially private algorithms that find $(α,Δ)$-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn $D_P(κ)$ into a "fat" region \emph{but only if} its volume is proportional to the volume of $D_P(κ-Δ)$. Lastly, we give a novel private algorithm that finds a depth parameter $κ$ for which the volume of $D_P(κ)$ is comparable to $D_P(κ-Δ)$. We hope this work leads to the further study of the intersection of differential privacy and computational geometry.