文章基本信息

标题：Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning
本地全文：下载
作者：Kunal Dutta ; Arijit Ghosh ; Bruno Jartoux 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：38:1-38:15
DOI：10.4230/LIPIcs.SoCG.2017.38
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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].
关键词：Epsilon-nets; Haussler's packing lemma; Mnets; shallow-cell complexity; shallow packing lemma