Some new bounds for Epsilon-nets

ABSTRACT

Given any natural number d, 0 < &egr; < 1, let ƒd(&egr;) denote the smallest integer ƒ such that every range space of Vapnik-Chervonenkis dimension d has an &egr;-net of size at most ƒ We solve a problem of Haussler and Welzl by showing that if d ≥ 2, then ƒd(&egr;) > 1/48 d/&egr; log 1/ &egr; which is not far from being optimal, if d is fixed and &egr; → 0. Further, we prove that ƒ1(&egr;) = max(2,⌈1/&egr;⌉ - 1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.

REFERENCES

• 1: P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
• 2: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 3: B. Chazelle and 3. Friedman, A deterministic view of random sampling and its use in geometry, Proc. 29th IEEE FOCS, 1988, 539-549.
• 4: B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
• 5: K. Clarkson, New applications of random sampling in computational geometry, Discrete & Computational Geometry 2, 1987, 195-222.
• 6: K. Clarkson, H. Edelsbrunner~ L. Guibas, M. Sharir and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces, Proceedings 29th Annual Symposium on Computational Geometry, 1988, 568-579.
• 7: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 8: D. Haussler, E. Welzl, e-Nets and Simplex Range Queries, Discrete Comput. Geom. 2 (1987'), 127'- 151.
• 9: J. Matoušek, Construction of epsilon nets, Proceedings of the fifth annual symposium on Computational geometry, p.1-10, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73834]
• 10: Jiří Matoušek , Raimund Seidel , E. Welzl, How to net a lot with little: small &egr;-nets for disks and halfspaces, Proceedings of the sixth annual symposium on Computational geometry, p.16-22, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98530]
• 11: János Pach, Covering the plane with convex polygons, Discrete & Computational Geometry, v.1 n.1, p.73-81, 1986 [doi>10.1007/BF02187684]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms