# Online Epsilon Net and Piercing Set for Geometric Concepts

arXiv: https://arxiv.org/abs/2410.07059 · HTML: https://mlsanity.com/paper/2410.07059/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 9 Oct 2024.

## Builds on (most cited first, 11 of 11)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching](https://mlsanity.com/paper/2407.20659/) (2024)
- [Online unit clustering in higher dimensions](https://mlsanity.com/paper/1708.02662/) (2017)
- [Online Unit Covering in Euclidean Space](https://mlsanity.com/paper/1710.00954/) (2017)
- [Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set](https://mlsanity.com/paper/2303.09524/) (2023)
- [Online Geometric Covering and Piercing](https://mlsanity.com/paper/2305.02445/) (2023)
- [Online hitting set of d-dimensional fat objects](https://mlsanity.com/paper/2309.02269/) (2023)
- [Fast Approximation Algorithms for Piercing Boxes by Points](https://mlsanity.com/paper/2311.02050/) (2023)
- [New Lower Bound and Algorithms for Online Geometric Hitting Set Problem](https://mlsanity.com/paper/2409.11166/) (2024)

## Built on by (most cited first, 2 of 2)

- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Representative Action Selection for Large Action Space Bandit Families](https://mlsanity.com/paper/2505.18269/) (2025)

## Abstract (arXiv)

VC-dimension and varepsilon-nets are key concepts in Statistical Learning Theory. Intuitively, VC-dimension is a measure of the size of a class of sets. The famous varepsilon-net theorem, a fundamental result in Discrete Geometry, asserts that if the VC-dimension of a set system is bounded, then a small sample exists that intersects all sufficiently large sets. In online learning scenarios where data arrives sequentially, the VC-dimension helps to bound the complexity of the set system, and varepsilon-nets ensure the selection of a small representative set. This sampling framework is crucial in various domains, including spatial data analysis, motion planning in dynamic environments, optimization of sensor networks, and feature extraction in computer vision, among others. Motivated by these applications, we study the online varepsilon-net problem for geometric concepts with bounded VC-dimension. While the offline version of this problem has been extensively studied, surprisingly, there are no known theoretical results for the online version to date. We present the first deterministic online algorithm with an optimal competitive ratio for intervals in ℝ. Next, we give a randomized online algorithm with a near-optimal competitive ratio for axis-aligned boxes in ℝd, for d≤ 3. Furthermore, we introduce a novel technique to analyze similar-sized objects of constant description complexity in ℝd, which may be of independent interest. Next, we focus on the continuous version of this problem, where ranges of the set system are geometric concepts in ℝd arriving in an online manner, but the universe is the entire space, and the objective is to choose a small sample that intersects all the ranges.