# Private Approximations of a Convex Hull in Low Dimensions

arXiv: https://arxiv.org/abs/2007.08110 · HTML: https://mlsanity.com/paper/2007.08110/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 2 of 2)

- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)

## Abstract (arXiv)

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 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 kappa-Tukey region induced by P (all points of Tukey-depth kappa or greater). Moreover, our approximations are all bi-criteria: for any geometric feature μ our (α,Delta)-approximation is a value "sandwiched" between (1-α)μ(DP(kappa)) and (1+α)μ(DP(kappa-Delta)). Our work is aimed at producing a (α,Delta)-kernel of DP(kappa), namely a set S such that (after a shift) it holds that (1-α)DP(kappa)subset mathsfCH(S) subset (1+α)DP(kappa-Delta). We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by Agarwal et al~[2004], 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 (α,Delta)-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn DP(kappa) into a "fat" region but only if its volume is proportional to the volume of DP(kappa-Delta). Lastly, we give a novel private algorithm that finds a depth parameter kappa for which the volume of DP(kappa) is comparable to DP(kappa-Delta). We hope this work leads to the further study of the intersection of differential privacy and computational geometry.