ALMOST TIGHT BOUNDS FOR EPSILON-NETS

被引：78

作者：

KOMLOS, J

PACH, J

WOEGINGER, G

机构：

[1] HUNGARIAN ACAD SCI,INST MATH,H-1364 BUDAPEST,HUNGARY

[2] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

[3] GRAZ TECH UNIV,INST MATH,A-8010 GRAZ,AUSTRIA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1992年 / 7卷 / 02期

关键词：

D O I：

10.1007/BF02187833

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given any natural number d, 0 < epsilon < 1, let f(d)(epsilon) denote the smallest integer f such that every range space of Vapnik-Chervonenkis dimension d has an epsilon-net of size at most f. We solve a problem of Haussler and Welzl by showing that if d greater-than-or-equal-to 2, then [GRAPHICS] Further, we prove that f1(epsilon) = max(2, inverted right perpendicular 1/epsilon inverted left perpendicular - 1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.

引用

页码：163 / 173

页数：11

共 13 条

[1]

AGARWAL PK, 1990, DISCRETE COMPUTATION, V5

[2]

BLUMER A, 1989, J ASS COMPUTING MACH, V36

[3]

Chazelle B., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P539, DOI 10.1109/SFCS.1988.21970

[4] QUASI-OPTIMAL RANGE SEARCHING IN SPACES OF FINITE VC-DIMENSION [J].