Almost tight bounds for $\epsilon$-nets

J. Komlós, J. Pach, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    83 Citations (Scopus)

    Abstract

    Given any natural numberd, 0<d - 2 + \frac2d + 2 \leqslant lime® 0 \fracfd (e)(1/e)log(1/e) \leqslant d.Unknown control sequence '\leqslant' Further, we prove thatf 1()=max(2, 1/ –1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.
    Original languageEnglish
    Pages (from-to)163-173
    Number of pages11
    JournalDiscrete and Computational Geometry
    Volume7
    Issue number1
    DOIs
    Publication statusPublished - 1992

    Fingerprint Dive into the research topics of 'Almost tight bounds for $\epsilon$-nets'. Together they form a unique fingerprint.

    Cite this