Document Open Access Logo

On Weak epsilon-Nets and the Radon Number

Authors Shay Moran, Amir Yehudayoff

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.51.pdf
  • Filesize: 496 kB
  • 14 pages

Document Identifiers

Author Details

Shay Moran
  • Department of Computer Science, Princeton University, Princeton, USA
Amir Yehudayoff
  • Department of Mathematics, Techion-IIT, Haifa, Israel

Funding

  • Moran, Shay: supported by the Simons Foundation and the NSF; part of this project was carried while the author was at the Institute for Advanced Study and was supported by the National Science Foundation under agreement No. CCF-1412958.
  • Yehudayoff, Amir: Research supported by ISF grant 1162/15. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.

Acknowledgements

We thank Noga Alon, Yuval Dagan, and Gil Kalai for helpful conversations. We also thank the anonymous reviewers assigned by SoCG '19 for their helpful comments which improved the presentation of this work.

Cite As Get BibTex

Shay Moran and Amir Yehudayoff. On Weak epsilon-Nets and the Radon Number. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.51

Abstract

We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove an amplification result for weak epsilon-nets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Combinatoric problems
Keywords
  • abstract convexity
  • weak epsilon nets
  • Radon number
  • VC dimension
  • Haussler packing lemma
  • Kneser graphs

Metrics

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

References

  1. Noga Alon. Private communication. Google Scholar
  2. Noga Alon. A Non-linear Lower Bound for Planar Epsilon-nets. Discrete & Computational Geometry, 47(2):235-244, 2012. URL: http://dx.doi.org/10.1007/s00454-010-9323-7.
  3. Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J Kleitman. Point selections and weak ε-nets for convex hulls. Combinatorics, Probability and Computing, 1(03):189-200, 1992. Google Scholar
  4. Noga Alon, Gil Kalai, Jiri Matousek, and Roy Meshulam. Transversal numbers for hypergraphs arising in geometry. Advances in Applied Mathematics, 29(1):79-101, 2002. Google Scholar
  5. Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, and Shakhar Smorodinsky. Weak ε-nets and interval chains. J. ACM, 55(6):28:1-28:32, 2008. URL: http://dx.doi.org/10.1145/1455248.1455252.
  6. Noga Alon and Daniel J Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem. Advances in Mathematics, 96(1):103-112, 1992. Google Scholar
  7. Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley &Sons, Inc., 2000. Google Scholar
  8. Imre Bárány, Zoltán Füredi, and László Lovász. On the number of halving planes. Combinatorica, 10(2):175-183, 1990. Google Scholar
  9. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach., 36(4):929-965, 1989. URL: http://dx.doi.org/10.1145/76359.76371.
  10. Boris Bukh, Jiří Matoušek, and Gabriel Nivasch. Lower bounds for weak epsilon-nets and stair-convexity. Israel Journal of Mathematics, 182(1):199-228, 2011. Google Scholar
  11. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. Improved bounds on weak ε-nets for convex sets. In STOC, pages 495-504, 1993. Google Scholar
  12. Victor Chepoi. Separation of two convex sets in convexity structures. Journal of Geometry, 50(1):30-51, 1994. URL: http://dx.doi.org/10.1007/BF01222661.
  13. L. Danzer, B. Grünbaum, and V. Klee. Helly’s Theorem and Its Relatives. Proceedings of symposia in pure mathematics: Convexity. American Mathematical Society, 1963. URL: https://books.google.com/books?id=I1l5HAAACAAJ.
  14. Esther Ezra. A note about weak epsilon-nets for axis-parallel boxes in d-space. Inf. Process. Lett., 110(18-19):835-840, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.06.005.
  15. Branko Grünbaum and Theodore S. Motzkin. On Components in Some Families of Sets. Proceedings of the American Mathematical Society, 12(4):607-613, 1961. URL: http://www.jstor.org/stable/2034254.
  16. Hugo Hadwiger and H Debrunner. Über eine variante zum hellyschen satz. Archiv der Mathematik, 8(4):309-313, 1957. Google Scholar
  17. P.C. Hammer. Semispaces and the Topology of Convexity, 1961. URL: https://books.google.com/books?id=0Vk_ngAACAAJ.
  18. Preston C. Hammer. Maximal convex sets. Duke Math. J., 22(1):103-106, March 1955. URL: http://dx.doi.org/10.1215/S0012-7094-55-02209-2.
  19. David Haussler. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995. Google Scholar
  20. David Haussler and Emo Welzl. Epsilon-Nets and Simplex Range Queries. Discrete & Computational Geometry, 2:127-151, 1987. Google Scholar
  21. David Kay and Eugene W Womble. Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers. Pacific Journal of Mathematics, 38(2):471-485, 1971. Google Scholar
  22. V. L. Klee. The Structure Of Semispaces. Mathematica Scandinavica, 4(1):54-64, 1956. URL: http://www.jstor.org/stable/24490011.
  23. D. J. Kleitman. Families of non-disjoint subsets. J. Combinatorial Theory, pages 153-155, 1966. Google Scholar
  24. Friedrich W Levi. On Helly’s theorem and the axioms of convexity. J. Indian Math. Soc, 15:65-76, 1951. Google Scholar
  25. László Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319-324, 1978. Google Scholar
  26. Jiří Matoušek. A Lower Bound for Weak epsilon-Nets in High Dimension. Discrete & Computational Geometry, 28(1):45-48, 2002. URL: http://dx.doi.org/10.1007/s00454-001-0090-3.
  27. Shmuel Onn. On the Geometry and Computational Complexity of Radon Partitions in the Integer Lattice. SIAM J. Discrete Math., 4(3):436-447, 1991. URL: http://dx.doi.org/10.1137/0404039.
  28. Natan Rubin. An Improved Bound for Weak Epsilon-Nets in the Plane. In FOCS, pages 224-235. IEEE Computer Society, 2018. Google Scholar
  29. Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. Google Scholar
  30. M.L.J. van de Vel. Theory of Convex Structures, volume 50 of North-Holland mathematical library. North-Holland, 1993. URL: https://books.google.com/books?id=xt9-lAEACAAJ.
  31. Roberta S Wenocur and Richard M Dudley. Some special vapnik-chervonenkis classes. Discrete Mathematics, 33(3):313-318, 1981. 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 About DROPS Imprint Privacy Contact