Document Open Access Logo

Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

Authors Kunal Dutta, Arijit Ghosh, Bruno Jartoux, Nabil H. Mustafa

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.38.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Kunal Dutta
Arijit Ghosh
Bruno Jartoux
Nabil H. Mustafa

Cite AsGet BibTex

Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.38

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].
Keywords
  • Epsilon-nets
  • Haussler's packing lemma
  • Mnets
  • shallow-cell complexity
  • shallow packing lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal, J. Pach, and M. Sharir. State of the Union (of Geometric Objects): A Review. In J. Goodman, J. Pach, and R. Pollack, editors, Computational Geometry: Twenty Years Later, pages 9-48. American Mathematical Society, 2008. Google Scholar
  2. B. Aronov, M. de Berg, E. Ezra, and M. Sharir. Improved Bounds for the Union of Locally Fat Objects in the Plane. SIAM J. Comput., 43(2):543-572, 2014. Google Scholar
  3. S. Arya, G. D. da Fonseca, and D. M. Mount. Optimal Area-Sensitive Bounds for Polytope Approximation. In Proc. 28th Annual Symposium on Computational Geometry (SoCG), pages 363-372, 2012. Google Scholar
  4. S. Arya, G. D. da Fonseca, and D. M. Mount. On the Combinatorial Complexity of Approximating Polytopes. In Proc. 32nd International Symposium on Computational Geometry (SoCG), volume 51, pages 11:1-11:15, 2016. Google Scholar
  5. S. Basu, R. Pollack, and M. F. Roy. Algorithms in Real Algebraic Geometry. Springer-Verlag, 2003. Google Scholar
  6. T. M. Chan, E. Grant, J. Könemann, and M. Sharpe. Weighted Capacitated, Priority, and Geometric Set Cover via Improved Quasi-Uniform Sampling. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1576-1585, 2012. Google Scholar
  7. B. Chazelle. A note on Haussler’s packing lemma. See Section 5.3 from Geometric Discrepancy: An Illustrated Guide by J. Matoušek, 1992. Google Scholar
  8. B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge, New York, 2000. Google Scholar
  9. K. Dutta, E. Ezra, and A. Ghosh. Two Proofs for Shallow Packings. Discrete &Computational Geometry, 56(4):910-939, 2016. Extended abstract appeared in Proc. 31st International Symposium on Computational Geometry (SoCG), pages 96-110, 2015. Google Scholar
  10. A. Ene, S. Har-Peled, and B. Raichel. Geometric Packing under Non-uniform Constraints. In Proc. 28th Annual Symposium on Computational Geometry (SoCG), pages 11-20, 2012. Google Scholar
  11. E. Ezra. A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension. SIAM J. Comput., 45(1):84-101, 2016. Extended abstract appeared in Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1378-1388, 2014. Google Scholar
  12. E. Ezra, B. Aronov, and S. Sharir. Improved Bound for the Union of Fat Triangles. In Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1778-1785, 2011. Google Scholar
  13. J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. A Semi-Algebraic Version of Zarankiewicz’s Problem. J. of the European Mathematical Society, to appear. Google Scholar
  14. L. Guth and N. H. Katz. On the Erdös distinct distances problem in the plane. Annals of Math., 181(1):155-190, 2015. Google Scholar
  15. D. Haussler. Sphere Packing Numbers for Subsets of the Boolean n-Cube with Bounded Vapnik-Chervonenkis Dimension. J. Comb. Theory, Ser. A, 69(2):217-232, 1995. Google Scholar
  16. D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete &Computational Geometry, 2:127-151, 1987. Google Scholar
  17. A. Kupavskii, N. H. Mustafa, and J. Pach. Near-Optimal Lower Bounds for ε-nets for Half-spaces and Low Complexity Set Systems. In M. Loebl, J. Nešetřil, and R. Thomas, editors, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek. Springer, 2017. Extended abstract with the title "New Lower Bounds for epsilon-Nets" appeared in Proc. 32nd International Symposium on Computational Geometry (SoCG), 54:1-54:16, 2016. Google Scholar
  18. Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. J. of Computer and System Sciences, 62(3):516-527, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1741.
  19. A. M. Macbeath. A theorem on non-homogeneous lattices. Annals of Math., 56:269-293, 1952. Google Scholar
  20. J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics. Springer, Berlin, New York, 1999. Google Scholar
  21. J. Matoušek. Lectures in Discrete Geometry. Springer-Verlag, New York, NY, 2002. Google Scholar
  22. J. Matoušek, J. Pach, M. Sharir, S. Sifrony, and E. Welzl. Fat Triangles Determine Linearly Many Holes. SIAM J. Comput., 23(1):154-169, 1994. Google Scholar
  23. J. Matoušek and Z. Patáková. Multilevel Polynomial Partitions and Simplified Range Searching. Discrete &Computational Geometry, 54(1):22-41, 2015. Google Scholar
  24. N. H. Mustafa. A Simple Proof of the Shallow Packing Lemma. Discrete &Computational Geometry, 55(3):739-743, 2016. Google Scholar
  25. N. H. Mustafa, K. Dutta, and A. Ghosh. A Simple Proof of Optimal Epsilon-nets. Combinatorica, to appear. Google Scholar
  26. N. H. Mustafa and S. Ray. ε -Mnets: Hitting Geometric Set Systems with Subsets. Discrete &Computational Geometry, 57(3):625-640, 2017. Extended abstract with the title "Near-Optimal Generalisations of a Theorem of Macbeath" appeared in Proc. 31st Symposium on Theoretical Aspects of Computer Science (STACS), pages 578-589, 2014. Google Scholar
  27. N. H. Mustafa and K. Varadarajan. Epsilon-approximations and Epsilon-nets. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, 2017. Google Scholar
  28. J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley &Sons, New York, NY, 1995. Google Scholar
  29. N. Sauer. On the Density of Families of Sets. J. Comb. Theory, Ser. A, 13(1):145-147, 1972. Google Scholar
  30. S. Shelah. A Combinatorial Problem, Stability and Order for Models and Theories in Infinitary Languages. Pacific J. of Mathematics, 41:247-261, 1972. Google Scholar
  31. K. R. Varadarajan. Weighted Geometric Set Cover via Quasi-Uniform Sampling. In Proc. 42nd Symposium on Theory of Computing (STOC), pages 641-648, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact