New existence proofs for ε-nets

Evangelia Pyrga, Saurabh Ray

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

Abstract

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
Pages199-207
Number of pages9
DOIs
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

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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

  • Cite this

    Pyrga, E., & Ray, S. (2008). New existence proofs for ε-nets. In Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 (pp. 199-207). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1377676.1377708