Small weak epsilon-nets

AbstractGiven 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 (e.g., 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 εiS, the smallest epsilon that can be guaranteed for any P when |Q|=i, for small values of i