Small weak epsilon-nets Academic Article uri icon


  • Abstract Given a set P of points in the plane, a set of points Q is a weak ε-net with respect to a family of sets S (eg, rectangles, disks, or convex sets) if every set of S containing ε| P| points contains a point of Q. In this paper, we determine bounds on ε i S, the smallest epsilon that can be guaranteed for any P when| Q|= i, for small values of i.

publication date

  • January 1, 2009