New Existence Proofs for Epsilon-nets

Abstract

We describe a new technique for proving the existence of small $\\eps$-nets for\nhypergraphs satisfying certain simple conditions. The technique is \nparticularlyuseful for proving $o(\\frac{1}{\\eps}\\log{\\frac{1}{\\eps}})$ upper \nbounds which\nis not possible using the standard VC dimension theory. We apply the technique\nto several geometric hypergraphs and obtain simple proofs for the existence of\n$O(\\frac{1}{\\eps})$ size $\\eps$-nets for them. This includes the geometric\nhypergraph in which the vertex set is a set of points in the plane and the\nhyperedges are defined by a set of pseudo-disks. This result was not known\npreviously. We also get a very short proof for the existence of \n$O(\\frac{1}{\\eps})$ size\n$\\eps$-nets for half\\-spaces in $\\Re^3$.