Epsilon-Nets

Imagine you are running a survey. You have a million customers and hundreds of market segments — age brackets, spending tiers, regions. You cannot interview everyone, but you need a sample small enough to be practical yet representative enough that no large segment is completely missed.

This is the problem that epsilon-nets solve, and the answer is surprisingly clean: you need only $O\!\left(\frac{d}{\varepsilon}\log\frac{d}{\varepsilon}\right)$ points, where $\varepsilon$ is how "large" a range must be before you guarantee hitting it, and $d$ is the VC-dimension — a single number that measures how richly the ranges can vary. Crucially, that bound does not depend on the size of the universe at all.

The concept was pinned down by David Haussler and Emo Welzl in 1987, building on Vapnik and Chervonenkis's earlier work on learning theory. It unlocked fast algorithms for range searching, randomized geometry, and became a cornerstone of PAC learning.

The canvas below shows 50 random points (the universe) and a family of axis-aligned rectangular ranges. A net point is shown in red; range rectangles are drawn in blue. Click Build $\varepsilon$-net to sample a net that stabs every rectangle containing at least $\varepsilon$ fraction of the points. Use the slider to change $\varepsilon$ and watch how the net grows as you demand coverage of smaller ranges.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label for="eps-slider">{{lbl_epsilon}} <strong id="eps-val">0.20</strong></label>
  <input id="eps-slider" type="range" min="0.05" max="0.50" step="0.05" value="0.20">
  <button id="btn-build" type="button">{{btn_build}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="440" height="300"></canvas>
<div id="status" class="status">{{status_initial}}</div>
<div class="legend">
  <span class="dot univ"></span> {{lbl_universe}}
  <span class="dot net"></span> {{lbl_net}}
  <span class="box-samp"></span> {{lbl_ranges}}
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .5rem; }
label { font-size: .9rem; }
input[type=range] { flex: 1 1 120px; min-width: 80px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.legend { display: flex; align-items: center; gap: .6rem; font-size: .82rem; flex-wrap: wrap; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.univ { background: #adb1b8; }
.dot.net  { background: #e63946; }
.box-samp { display: inline-block; width: 14px; height: 10px;
            border: 1.5px solid #457b9d; background: rgba(69,123,157,.12); border-radius: 2px; }

// Code not found

Notice that the net size stays small even though the universe has 50 points. When $\varepsilon = 0.2$ a range must contain at least 10 points before the net is required to hit it — and a handful of net points suffices. Lower $\varepsilon$ forces coverage of smaller ranges and the net grows, but always far below the universe size. That is the epsilon-net guarantee at work.

The key insight is that you can ignore most of the universe.

Definitions. A set system $(X, \mathcal{R})$ pairs a universe $X$ with a family of subsets $\mathcal{R}$ called ranges. A set $N \subseteq X$ is an $\varepsilon$-net for $(X, \mathcal{R})$ if every range $R \in \mathcal{R}$ with $|R| \ge \varepsilon |X|$ contains at least one point of $N$.

VC-dimension. The VC-dimension $d$ of $(X, \mathcal{R})$ is the size of the largest subset $S \subseteq X$ shattered by $\mathcal{R}$ — meaning every possible subset of $S$ is realised as $R \cap S$ for some $R \in \mathcal{R}$. For axis-aligned rectangles in the plane, $d = 4$; for halfplanes, $d = 3$.

The theorem (Haussler–Welzl 1987). Every set system of VC-dimension $d$ has an $\varepsilon$-net of size at most

$$O\!\left(\frac{d}{\varepsilon}\log\frac{d}{\varepsilon}\right).$$

This bound is nearly tight: there are set systems requiring $\Omega\!\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ points. A later breakthrough by Komlós, Pach and Woeginger (1992) showed that for geometric set systems of bounded VC-dimension you can sometimes do better — $O(d/\varepsilon)$ — matching a lower bound.

Why it matters for algorithms. Range-searching data structures, cuttings, and PAC learning all reduce to: "find a small set that witnesses every heavy range." The epsilon-net theorem says a random sample of size $O\!\left(\frac{d}{\varepsilon}\log\frac{d}{\varepsilon}\right)$ works with high probability, giving a clean randomised construction. This connects directly to the VC-dimension analysis in learning theory and underpins sample-complexity bounds across machine learning.

The epsilon-net theorem is a Swiss-army knife for algorithm designers whenever "sample a little, cover a lot" is needed:

• Geometric range searching: partition a point set into cells so that no cell is hit too often. An $\varepsilon$-cutting built from an $\varepsilon$-net answers half-plane or ball queries in $O(\sqrt{n})$ time instead of $O(n)$.
• Randomized cuttings: Clarkson's algorithm for linear programming in fixed dimension uses epsilon-nets to reduce the active set at each step.
• Approximate nearest-neighbor: locality-sensitive hashing schemes implicitly build epsilon-nets over distance ranges.
• PAC learning: the sample complexity of learning a concept class of VC-dimension $d$ is $O\!\left(\frac{d}{\varepsilon}\log\frac{d}{\varepsilon}\right)$ — exactly the epsilon-net bound. Seeing why learning and geometry share the same formula is one of the most elegant connections in theoretical computer science.
• Sensor placement and coverage: place the fewest sensors so that every "large" region of interest has at least one sensor inside it — an epsilon-net in disguise.

Whenever a problem asks for a small certificate that rules out large violations, look for a set system with bounded VC-dimension and reach for the epsilon-net theorem.

Epsilon-nets reveal a surprising truth: the richness of a set system, measured by its VC-dimension, is all that controls how small a representative sample needs to be. A universe of a million points and a universe of ten points need the same net size, as long as the ranges are equally complex.

That independence from universe size is what makes epsilon-nets so powerful in algorithm design — you can always afford the sample. And because PAC learning and geometric range searching share the same VC-dimension formula, a single elegant theorem bridges machine learning and computational geometry, showing that two seemingly distant fields are really asking the same question.