Item

Abstract

We describe a new technique for proving the existence of small $\eps$-nets for hypergraphs satisfying certain simple conditions. The technique is particularlyuseful for proving $o(\frac{1}{\eps}\log{\frac{1}{\eps}})$ 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 $O(\frac{1}{\eps})$ size $\eps$-nets for them. This includes the geometric hypergraph in which 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(\frac{1}{\eps})$ size $\eps$-nets for half\-spaces in $\Re^3$.