Imagine you have a large collection of points scattered across a space, and you want to select a small subset of "sentinel" points. Your goal is simple: any region of a certain shape (like a circle, rectangle, or convex hull) that contains a significant fraction—say, more than $\epsilon$—of the total points must contain at least one of your sentinels.
This chosen subset is called an $\epsilon$-net. $\epsilon$-nets are foundational tools in computational geometry, learning theory, and optimization because they allow us to discretize continuous or massive spaces without losing structural information.
For decades, the size and existence of these nets were thought to be governed almost entirely by Vapnik-Chervonenkis (VC) dimension. However, when dealing with complex geometric structures like convex hulls, standard VC dimension theory breaks down. Recent breakthroughs have revealed a deeper, more fundamental combinatorial metric that dictates when and why we can efficiently pierce these spaces: the Radon number.
When VC Dimension Fails: Strong vs. Weak Nets
To understand why the Radon number is necessary, we must first distinguish between two types of nets:
- Strong $\epsilon$-nets: The sentinel points must be chosen from the original input point set.
- Weak $\epsilon$-nets: The sentinel points can be placed anywhere in the ambient space.
If we restrict ourselves to strong $\epsilon$-nets, our success depends entirely on the VC dimension of the ranges we want to pierce. If the VC dimension is finite, we can always find a small strong $\epsilon$-net.
But consider convex sets. If we place points along the circumference of a circle, every single subset of these points can be isolated by a convex polygon. This means the collection of all possible convex hulls has an infinite VC dimension. Consequently, finding a small strong $\epsilon$-net is impossible; you cannot guarantee piercing every heavy convex region using only a small subset of the original points.
However, if we switch to weak $\epsilon$-nets, the rules change. By allowing ourselves the freedom to place sentinel points anywhere in the space—such as inside the center of the circle—we can manage the complexity of these infinite ranges.
Grigni et al. demonstrated this phenomenon by showing that weak $\epsilon$-nets for convex hulls can achieve a polynomial size relative to $1/\epsilon$, completely bypassing the infinite VC-dimension barrier. The flexibility to pick points outside the original set fundamentally alters the complexity of the problem, but it raises a critical question: if VC dimension doesn't govern the existence of weak $\epsilon$-nets, what does?
The Radon Number as a Universal Threshold
The answer lies in an abstract combinatorial property known as the Radon number. In classical geometry, Radon's theorem states that any set of $d+2$ points in a $d$-dimensional Euclidean space can be partitioned into two disjoint subsets whose convex hulls intersect.
In a pair of foundational papers, Moran et al. (2019) and Moran et al. (2020) extended this concept to abstract "convexity spaces"—spaces defined not by coordinates, but purely by abstract rules of closure and containment. They established that the Radon number serves as the ultimate combinatorial threshold for weak $\epsilon$-nets.
Specifically, the authors proved that in compact separable convexity spaces, a finite Radon number is both necessary and sufficient for the existence of weak $\epsilon$-nets of finite size for any $\epsilon > 0$.
Why does this work intuitively? If a space has a finite Radon number $r$, it means that you can never find $r$ points that are completely independent of one another; any large enough group of points will naturally "clump" together such that their convex closures overlap. This topological constraint prevents the space from exhibiting chaotic, infinitely branching behavior. By leveraging the interplay between the Radon number, Helly numbers, and localized VC dimension, the authors showed how to construct a finite set of piercing points that are guaranteed to intercept any region containing an $\epsilon$-mass of points.
Refining and Generalizing the Bounds
With the qualitative question of existence settled by the Radon number, a parallel line of research focuses on optimizing the size and algorithmic efficiency of these nets using refined complexity measures.
Matrix Cover Numbers
The utility of bounding these nets extends directly into matrix theory and algorithms. Lee et al. analyzed the "cover number" of a matrix—the number of small cubes needed to cover the convex hull of the matrix's columns. They demonstrated that the VC dimension of a matrix provides a powerful upper bound on this cover number, scaling as $n^{O(VC(A)/\epsilon^2)}$. Because this VC dimension is often logarithmic relative to the matrix dimensions, it enables the efficient construction of $\epsilon$-nets applied to algorithmic game theory, such as finding approximate Nash equilibria.
Beyond Standard Nets: $\epsilon$-t-Nets
In many applications, merely hitting a set with one point is insufficient; we might require a higher degree of intersection. Jartoux et al. generalized the problem to $\epsilon$-t-nets, where the goal is to pierce hyperedges using subsets of size $t$. To achieve this, the authors introduced the $t$-VC-dimension, a refined parameter that captures how subsets of size $t$ are shattered. This parameter allows for deterministic, simpler net constructions that avoid complex derandomization techniques while providing tight, explicit size bounds.
Alternative Capacity Measures
To push the bounds of $\epsilon$-nets even closer to optimality, researchers have looked beyond standard dimensions to more granular geometric properties:
- Shallow Cell Complexity: Mustafa et al. provided a simplified, unified framework for proving optimal $\epsilon$-net bounds. They showed that instead of relying on coarse measures like the standard VC dimension, analyzing the local, shallow cell complexity of geometric arrangements yields much tighter, more accessible proofs for optimal net sizes.
- Alexander's Capacity: Kupavskii et al. leveraged a structural measure known as Alexander's capacity. They proved that when this capacity remains constant, $\epsilon$-net bounds can be dramatically compressed to $O(\log \epsilon)$, offering a massive improvement over standard VC-dependent bounds.
Summary
The evolution of $\epsilon$-net theory demonstrates that the complexity of a space depends heavily on how we are allowed to interact with it. While strong $\epsilon$-nets are strictly bound to the confines of VC dimension, weak $\epsilon$-nets exploit the global geometry of the ambient space. By identifying the Radon number as the functional equivalent of the VC dimension for weak piercing sets, this line of research provides a complete combinatorial characterization of abstract spaces, explaining precisely when and why complex geometric ranges can be efficiently summarized by a handful of points.
Key Foundational Work
The Cover Number of a Matrix and its Algorithmic Applications (2014) — contributed 2 concept elements to this direction.
Improved Bounds on Weak epsilon-Nets for Convex Sets (1995) — contributed 1 concept elements to this direction.