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 -