2026-07-21T19:26:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7199 2024-03-06T10:40:01Z ddc:004 open_access

Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning Dutta, Kunal Ghosh, Arijit Jartoux, Bruno Mustafa, Nabil H. Epsilon-nets Haussler's packing lemma Mnets shallow-cell complexity shallow packing lemma The packing lemma of Haussler states that given a set system (X,R) with bounded VC dimension, if every pair of sets in R have large symmetric difference, then R cannot contain too many sets. Recently it was generalized to the shallow packing lemma, applying to set systems as a function of their shallow-cell complexity. In this paper we present several new results and applications related to packings: * an optimal lower bound for shallow packings, * improved bounds on Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry, * we observe that Mnets provide a general, more powerful framework from which the state-of-the-art unweighted epsilon-net results follow immediately, and * simplifying and generalizing one of the main technical tools in [Fox et al. , J. of the EMS, to appear]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kunal Dutta and Arijit Ghosh and Bruno Jartoux and Nabil H. Mustafa 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.38 urn:nbn:de:0030-drops-71991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.38 eng https://creativecommons.org/licenses/by/3.0/legalcode