New existence proofs ε-nets

Abstract

We describe a new technique for proving the existence of small μ-nets for hypergraphs satisfying certain simple conditions. The technique is particularly useful for proving o(1/μ log 1/μ) upper bounds which the standard VC-dimension theory does not allow. We apply the technique to several geometric hypergraphs and obtain simple proofs for the existence of O(1/μ) size μ-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 O(1/μ) size μ-nets for half-spaces in R3.