@inproceedings{9543cce29da8428e94c96757b06e178f,

title = "New existence proofs for ε-nets",

abstract = "We describe a new technique for proving the existence of small e-nets for hypergraphs satisfying certain simple conditions. The technique is particularly useful for proving O(1/ε log 1/ε) upper bounds which is not possible using the standard VC dimension theory. We apply the technique to several geometric hypergraphs and obtain simple proofs for the existence of ( ε1) size ε-nets for them. This includes the geometric hypergraph in wdiich the vertex set is a set of points in the plane and the hyperedges are defined by a set of pseudo-disks. This result was not known previously. We also get a very short proof for the existence of O( ε1/ε) size ε-nets for halfspaces in Double strok R sign.",

keywords = "Discrete geometry, Hitting sets, Hypergraph transversals, Strong ε-nets",

author = "Evangelia Pyrga and Saurabh Ray",

year = "2008",

doi = "10.1145/1377676.1377708",

language = "English (US)",

isbn = "9781605580715",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "199--207",

booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",

note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",

}