Small strong epsilon nets ?
Let P be a set of n  points in Rd R d . A point x is said to be a centerpoint of P if x  is contained in every convex object that contains more than d n d + 1 points of P. We call a point x a strong centerpoint  for a family of objects C C if x?P x ? P is contained in every object C?C C ? C that contains more than a constant fraction of points of P . A strong centerpoint does not exist even for halfspaces in R2 R 2 . We prove that a strong centerpoint exists for axis-parallel boxes in Rd R d and give exact bounds. We then extend this to small strong ? -nets in the plane. Let ? i S represent the smallest real number in [0,1] [ 0 , 1 ] such that there exists an ? i S -net of size i  with respect to S S . We prove upper and lower bounds for ? i S where S S is the family of axis-parallel rectangles, halfspaces and disks.
centerpoint ?-nets axis-parallel rectangles small weak ?-nets