caa a22 4500 469075392 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920201xx s 000 0 eng 10.1007/BF02187833 doi (NATIONALLICENCE)springer-10.1007/BF02187833 Almost tight bounds for ɛ -Nets [Elektronische Daten] [János Komlós, János Pach, Gerhard Woeginger] Given any natural numberd, 0<ɛ<1, letf d (ɛ) denote the smallest integerf such that every range space of Vapnik-Chervonenkis dimensiond has anɛ-net of size at mostf. We solve a problem of Haussler and Welzl by showing that ifd≥2, then % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrpepeei0xd9Wq-Jb9% vqaqFfpe0db9as0-LqLs-Jirpepeei0-bs0Fb9pgea0db9fr-xfr-x% frpeWZqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadsgacqGHsi% slcaaIYaGaey4kaSYaaSaaaeaacaaIYaaabaGaamizaiabgUcaRiaa% ikdaaaGaeyizIm6aaCbeaeaaciGGSbGaaiyAaiaac2gaaSqaaGGaai% ab-v7aLjabgkziUkaaicdaaeqaaOWaaSaaaeaacaWGMbWaiaoGBaaa% leacGdOaiaoGdsgaaeqcGdiakiacGZOGOaGamaoJ-v7aLjacGZOGPa% aabaGaaiikaiaaigdacaGGVaGae8xTduMaaiykaiGacYgacaGGVbGa% ai4zaiaacIcacaaIXaGaai4laiab-v7aLjaacMcaaaGaeyizImQaam% izaiaac6caaaa!65C6! $$d - 2 + \frac{2}{{d + 2}} \leqslant \mathop {\lim }\limits_{\varepsilon \to 0} \frac{{f_d (\varepsilon )}}{{(1/\varepsilon )\log (1/\varepsilon )}} \leqslant d.$$ 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. Springer-Verlag New York Inc., 1992 Komlós János Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA aut Pach János Mathematical Institute, Hungarian Academy of Sciences, Pf. 127, H-1364, Budapest, Hungary aut Woeginger Gerhard Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut Discrete & Computational Geometry Springer New York 7/2(1992-02-01), 163-173 0179-5376 7:2<163 1992 7 454 https://doi.org/10.1007/BF02187833 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187833 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Komlós János Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA aut NATIONALLICENCE 700 1- Pach János Mathematical Institute, Hungarian Academy of Sciences, Pf. 127, H-1364, Budapest, Hungary aut NATIONALLICENCE 700 1- Woeginger Gerhard Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/2(1992-02-01), 163-173 0179-5376 7:2<163 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer