Small weak epsilon nets

B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, S. Smorodinsky, and C. Seara

Abstract:

Let S be a family of sets in the plane. Let 0 < epsilon(S,i) < 1 denote the minimum real number such that for any finite point set P there exists a set Q of i points that is a weak epsilon(S,i)-net for P with respect to S. We derice upper and lower bounds on epsilon(S,i) for small integers i and when S is the family of all convex sets, or the family of all axis-parallel rectangles.



Reference: B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, S. Smorodinsky, and C. Seara. Small weak epsilon nets. In Proc. $17^{th}$ Canadian Conference on Computational Geometry CCCG '05, pages 51-54, Windsor, Ontario, 2005.