Almost tight bounds for $\epsilon$-nets

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

doi:10.1007/BF02187833

Almost tight bounds for $\epsilon$-nets

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

Research output: Contribution to journal › Article › Academic › peer-review

93 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 language	English
Pages (from-to)	163-173
Number of pages	11
Journal	Discrete and Computational Geometry
Volume	7
Issue number	1
DOIs	https://doi.org/10.1007/BF02187833
Publication status	Published - 1992

Access to Document

10.1007/BF02187833

Cite this

@article{eebca84036074458a5ac480c7fef0f4f,

title = "Almost tight bounds for $\epsilon$-nets",

abstract = "Given any natural numberd, 0<d - 2 + \frac2d + 2 \leqslant lime{\textregistered} 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.",

author = "J. Koml{\'o}s and J. Pach and G.J. Woeginger",

year = "1992",

doi = "10.1007/BF02187833",

language = "English",

volume = "7",

pages = "163--173",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Almost tight bounds for $\epsilon$-nets

AU - Komlós, J.

AU - Pach, J.

AU - Woeginger, G.J.

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

U2 - 10.1007/BF02187833

DO - 10.1007/BF02187833

M3 - Article

SN - 0179-5376

VL - 7

SP - 163

EP - 173

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Almost tight bounds for $\epsilon$-nets

Abstract

Access to Document

Fingerprint

Cite this