2026-07-20T05:38:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5149 2024-03-06T10:35:50Z ddc:004 open_access

Two Proofs for Shallow Packings Dutta, Kunal Ezra, Esther Ghosh, Arijit Set systems of bounded primal shatter dimension delta-packing & Haussler’s approach relative approximations Clarkson-Shor random sampling approach 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 n-point set X; we view V as a set of indicator vectors over the n-dimensional unit cube. A delta-separated 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 delta-packing number is then defined as the cardinality of the largest delta-separated subcollection of V. Haussler showed an asymptotically tight bound of Theta((n / delta)^d) on the delta-packing number if V has VC-dimension (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^{d-d_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 "k-shallow" (all vector lengths are at most k), we show that its delta-packing number is O(n^{d_1} k^{d-d_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kunal Dutta and Esther Ezra and Arijit Ghosh 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.96 urn:nbn:de:0030-drops-51493 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.96 eng https://creativecommons.org/licenses/by/3.0/legalcode