Research map / Learning theory and algorithms / Sample complexity
ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of online epsilon-nets and online piercing sets for geometric concepts, giving a deterministic optimal-ratio algorithm for intervals, randomized near-optimal algorithms for boxes in R^2/R^3, and deterministic O(log M) algorithms for boxes and ellipsoids in R^d.
Problem
Online epsilon-net and online piercing set problems for geometric concepts with bounded VC-dimension, where ranges arrive sequentially and the net/piercing set must be maintained irrevocably; prior online results were scarce for arbitrary-size objects.
Approach
Deterministic online algorithms that hit each heavy range at its median-indexed points (for intervals) or at range centers (for piercing), combined with randomized sampling plus range-tree-based safety nets for boxes, and an annular-block packing argument that bounds the number of algorithm points per optimal point by O(log M).
Key results
- Deterministic online epsilon-net for intervals with competitive ratio 2(log(1/eps)+1), matching the Omega(log n) lower bound.
- Randomized online epsilon-net for axis-aligned rectangles in R^2 with expected competitive ratio O(log(1/eps)); for boxes in R^3, O(log^3(1/eps)).
- Deterministic Algo-Center achieves O(log M) competitive ratio for piercing axis-aligned boxes and ellipsoids in R^d, asymptotically tight given the Omega(log M) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Algo-Fat with the revised layer and lattice selection | Online piercing of similarly-sized α-fat objects in ℝᵈ · Similarly-sized α-fat objects in ℝᵈ | competitive ratio: O\left((\frac{2}{\alpha}+2)^d \log M\right) -> O\left(\lfloor\frac{2}{\alpha}+\frac{7}{8}\rfloor^d\log M\right) | Helped |
Limitations
- Online epsilon-net results hold only for epsilon in a restricted regime (e.g., epsilon > 1/C) for rectangles and boxes.
- Box extension to R^d for d>=4 is not handled; the number of maximal unhit orthants can grow super-linearly.
- The rectangle lower-bound argument relies on an offline bound rather than an instance-optimal online lower bound.
Experimental setup
Metrics: competitive ratio
Baselines: Algo-Center De et al. fat-object algorithm
Builds on: epsilon-net theorem Even and Smorodinsky online hitting set Charikar et al. online piercing set De et al. online piercing of fat objects
Closest papers by meaning
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.84)
- Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.84)
- The Parameterized Complexity of Computing the VC-Dimension (NeurIPS 2025 · similarity 0.84)
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.83)
- Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.83)
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.