License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.18
URN: urn:nbn:de:0030-drops-143377
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14337/
Gao, Yue ;
Sheffet, Or
Differentially Private Approximations of a Convex Hull in Low Dimensions
Abstract
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 D_{P}(κ) - 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 (α,Δ)-kernel of D_P(κ), namely a set ? such that (after a shift) it holds that (1-α)D_P(κ) ⊂ CH(?) ⊂ (1+α)D_P(κ-Δ). We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by [Pankaj K. 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 (α,Δ)-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 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 the volume of D_P(κ-Δ). We hope our work leads to the further study of the intersection of differential privacy and computational geometry.
BibTeX - Entry
@InProceedings{gao_et_al:LIPIcs.ITC.2021.18,
author = {Gao, Yue and Sheffet, Or},
title = {{Differentially Private Approximations of a Convex Hull in Low Dimensions}},
booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-197-9},
ISSN = {1868-8969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14337},
URN = {urn:nbn:de:0030-drops-143377},
doi = {10.4230/LIPIcs.ITC.2021.18},
annote = {Keywords: Differential Privacy, Computational Geometry, Tukey Depth}
}
|
Keywords: |
|
Differential Privacy, Computational Geometry, Tukey Depth |
|
Collection: |
|
2nd Conference on Information-Theoretic Cryptography (ITC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
19.07.2021 |
