### Abstract

We study a natural generalization of the classical ε-net problem (Haussler-Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ _{n}^{t}, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least εn contains a set in S. When t = 1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O(^{(1+log ε t})^{d} log ^{1} ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(^{1} ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t = 1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

Original language | English (US) |
---|---|

Title of host publication | 36th International Symposium on Computational Geometry, SoCG 2020 |

Editors | Sergio Cabello, Danny Z. Chen |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771436 |

DOIs | |

State | Published - Jun 1 2020 |

Event | 36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland Duration: Jun 23 2020 → Jun 26 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 164 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 36th International Symposium on Computational Geometry, SoCG 2020 |
---|---|

Country | Switzerland |

City | Zurich |

Period | 6/23/20 → 6/26/20 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Epsilon-nets
- Geometric hypergraphs
- Linear union complexity
- VC-dimension

## Cite this

*36th International Symposium on Computational Geometry, SoCG 2020*[LIPIcs-SoCG-2020-5] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2020.5