2026-07-25T03:00:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10455 2024-03-06T10:46:02Z ddc:004 open_access

On Weak epsilon-Nets and the Radon Number Moran, Shay Yehudayoff, Amir abstract convexity weak epsilon nets Radon number VC dimension Haussler packing lemma Kneser graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shay Moran and Amir Yehudayoff 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.51 urn:nbn:de:0030-drops-104551 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.51 eng https://creativecommons.org/licenses/by/3.0/legalcode