2014/12/16 by Esther Ezra, Ezra, Esther
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1412.5215
arxiv created 2014/12/16 · arxiv updated 2014/12/18
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 δ-separated set of \V is a subcollection \W, s.t. the Hamming distance between each pair \uu, \vv ∈ \W is greater than δ, where δ> 0 is an integer parameter. The δ-packing number is then defined as the cardinality of the largest δ-separated subcollection of \V. Haussler showed an asymptotically tight bound of Θ((n/δ)d) on the δ-packing number if \V has VC-dimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X' ⊆ 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(md1 kd-d1), for a fixed integer d > 0 and a real parameter 1 ≤ d1 ≤ d (this generalizes the standard notion of bounded primal shatter dimension when d1 = d). In this case when \V is "k-shallow" (all vector lengths are at most k), we show that its δ-packing number is O(nd1 kd-d1/δd), matching Haussler's bound for the special cases where d1=d or k=n. As an immediate consequence we conclude that set systems of halfspaces, balls, and parallel slabs defined over n points in d-space admit better packing numbers when k is smaller than n. Last but not least, we describe applications to (i) spanning trees of low total crossing number, and (ii) geometric discrepancy, based on previous work by the author.