Abstract
We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an npoint set X; we view V as a set of indicator vectors over the ndimensional unit cube. A deltaseparated set of V is a subcollection W, s.t. the Hamming distance between each pair u, v in W is greater than delta, where delta > 0 is an integer parameter. The deltapacking number is then defined as the cardinality of the largest deltaseparated subcollection of V. Haussler showed an asymptotically tight bound of Theta((n / delta)^d) on the deltapacking number if V has VCdimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X' of X of size m <= n and for any parameter 1 <= k <= m, the number of vectors of length at most k in the restriction of V to X' is only O(m^{d_1} k^{dd_1}), for a fixed integer d > 0 and a real parameter 1 <= d_1 <= d (this generalizes the standard notion of bounded primal shatter dimension when d_1 = d). In this case when V is "kshallow" (all vector lengths are at most k), we show that its deltapacking number is O(n^{d_1} k^{dd_1} / delta^d), matching Haussler's bound for the special cases where d_1=d or k=n. We present two proofs, the first is an extension of Haussler's approach, and the second extends the proof of Chazelle, originally presented as a simplification for Haussler's proof.
BibTeX  Entry
@InProceedings{dutta_et_al:LIPIcs:2015:5149,
author = {Kunal Dutta and Esther Ezra and Arijit Ghosh},
title = {{Two Proofs for Shallow Packings}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {96110},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5149},
URN = {urn:nbn:de:0030drops51493},
doi = {10.4230/LIPIcs.SOCG.2015.96},
annote = {Keywords: Set systems of bounded primal shatter dimension, deltapacking & Haussler’s approach, relative approximations, ClarksonShor random sampling approach}
}
Keywords: 

Set systems of bounded primal shatter dimension, deltapacking & Haussler’s approach, relative approximations, ClarksonShor random sampling approach 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015) 
Issue Date: 

2015 
Date of publication: 

11.06.2015 