New existence proofs for ε-nets

Evangelia Pyrga, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Number of pages9
StatePublished - 2008
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Other24th Annual Symposium on Computational Geometry, SCG'08
Country/TerritoryUnited States
CityCollege Park, MD


  • Discrete geometry
  • Hitting sets
  • Hypergraph transversals
  • Strong ε-nets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'New existence proofs for ε-nets'. Together they form a unique fingerprint.

Cite this