Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.38
URN: urn:nbn:de:0030-drops-71991
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7199/
Dutta, Kunal ; Ghosh, Arijit ; Jartoux, Bruno ; Mustafa, Nabil H.
Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning
| pdf-format: |
|
Abstract
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].
BibTeX - Entry
@InProceedings{dutta_et_al:LIPIcs:2017:7199,
author = {Kunal Dutta and Arijit Ghosh and Bruno Jartoux and Nabil H. Mustafa},
title = {{Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {38:1--38:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-038-5},
ISSN = {1868-8969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7199},
URN = {urn:nbn:de:0030-drops-71991},
doi = {10.4230/LIPIcs.SoCG.2017.38},
annote = {Keywords: Epsilon-nets, Haussler's packing lemma, Mnets, shallow-cell complexity, shallow packing lemma}
}
| Keywords: | Epsilon-nets, Haussler's packing lemma, Mnets, shallow-cell complexity, shallow packing lemma | |
| Seminar: | 33rd International Symposium on Computational Geometry (SoCG 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 20.06.2017 |
