New Existence Proofs for Epsilon-nets
Evangelia Pyrga, Saurabh Ray · Max Planck Institute for Plasma Physics · 2008
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$.