### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 |

Pages | 199-207 |

Number of pages | 9 |

DOIs | |

State | Published - 2008 |

Event | 24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States Duration: Jun 9 2008 → Jun 11 2008 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 24th Annual Symposium on Computational Geometry, SCG'08 |
---|---|

Country | United States |

City | College Park, MD |

Period | 6/9/08 → 6/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

*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