TY - JOUR

T1 - Small weak epsilon-nets

AU - Aronov, Boris

AU - Aurenhammer, Franz

AU - Hurtado, Ferran

AU - Langerman, Stefan

AU - Rappaport, David

AU - Seara, Carlos

AU - Smorodinsky, Shakhar

N1 - Funding Information:
E-mail addresses: [email protected] (F. Aurenhammer), [email protected] (F. Hurtado), [email protected] (S. Langerman), [email protected] (D. Rappaport), [email protected] (C. Seara), [email protected] (S. Smorodinsky). URLs: http://cis.poly.edu/~aronov/ (B. Aronov), http://www.cs.bgu.ac.il/~shakhar/ (S. Smorodinsky). 1 Research supported by grant SAB2003-0097, Min. Educ. y Ciencia, España. Also partially supported by NSF ITR Grant CCR-00-81964 and by a grant from US–Israel Binational Science Foundation. 2 Supported by Accion Integrada Austria–Espana MCYT HU2002-0010 and Austrian FWF Joint Research Project ‘Industrial Geometry’ S9205-N12. 3 Partially supported by projects MCYT-FEDER-BFM2003-00368, Gen-Cat-2001SGR00224, Acción Integrada Austria–España MCYT HU2002-0010, MEC MTM2006-01267, and DURSI 2005SGR00692. 4 Maître de recherches du F.R.S.-FNRS. 5 Supported by NSERC of Canada Discovery Grant 9204. 6 Work on this paper was supported by the NSF Mathematical Sciences Postdoctoral Fellowship award 0402492.

PY - 2009/7

Y1 - 2009/7

N2 - 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 (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.

AB - 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 (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.

KW - Convex sets

KW - Rectangles

KW - Set systems

KW - Weak epsilon-nets

UR - http://www.scopus.com/inward/record.url?scp=84867987234&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867987234&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2008.02.005

DO - 10.1016/j.comgeo.2008.02.005

M3 - Article

AN - SCOPUS:84867987234

SN - 0925-7721

VL - 42

SP - 455

EP - 462

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 5

ER -