Epsilon-Nets

Introduction

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.

Try It: Build a Net

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.

<!-- Epsilon-net demo: build a small net that stabs every heavy range -->
<div class="controls">
  <label for="eps-slider">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">Build ε-net</button>
  <button id="btn-reset" type="button" class="ghost">New universe</button>
</div>
<canvas id="canvas" width="440" height="300"></canvas>
<div id="status" class="status">Click Build ε-net to sample a net.</div>
<div class="legend">
  <span class="dot univ"></span> universe
  <span class="dot net"></span> net point
  <span class="box-samp"></span> heavy ranges
</div>

/* Demo styles — canvas-based epsilon-net visualizer */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Epsilon-net demo: random universe of points + axis-aligned rectangle ranges.
const W = 440, H = 300;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('eps-slider');
const epsVal = document.getElementById('eps-val');
const statusEl = document.getElementById('status');

// Universe of random points drawn uniformly on the canvas
const MARGIN = 20;
const N_PTS = 50;
let universe = [];

function randInt(lo, hi) { return Math.floor(Math.random() * (hi - lo + 1)) + lo; }

function initUniverse() {
  // generate N_PTS uniformly random points
  universe = [];
  for (let i = 0; i < N_PTS; i++) {
    universe.push({ x: randInt(MARGIN, W - MARGIN), y: randInt(MARGIN, H - MARGIN) });
  }
}

// Build a pool of random axis-aligned rectangle ranges
function buildRanges() {
  const ranges = [];
  // generate 40 random rectangles of varying sizes
  for (let i = 0; i < 40; i++) {
    const x1 = randInt(MARGIN, W - MARGIN - 40);
    const y1 = randInt(MARGIN, H - MARGIN - 30);
    const x2 = randInt(x1 + 20, Math.min(x1 + 180, W - MARGIN));
    const y2 = randInt(y1 + 15, Math.min(y1 + 130, H - MARGIN));
    ranges.push({ x1, y1, x2, y2 });
  }
  return ranges;
}

// A range is heavy if it contains >= eps * |universe| points
function heavyRanges(ranges, eps) {
  const threshold = eps * universe.length;
  return ranges.filter(r => {
    const inside = universe.filter(p => p.x >= r.x1 && p.x <= r.x2 && p.y >= r.y1 && p.y <= r.y2);
    return inside.length >= threshold;
  });
}

// Greedy set-cover net: pick the point that stabs the most remaining heavy ranges
// This always finds a valid net (every heavy range gets stabbed) though not the smallest.
function buildNet(heavyRangesList, eps) {
  const net = [];
  let remaining = [...heavyRangesList];
  const candidates = [...universe];
  // greedy: always add the point hitting the most uncovered heavy ranges
  while (remaining.length > 0 && candidates.length > 0) {
    let bestIdx = 0, bestHit = 0;
    for (let i = 0; i < candidates.length; i++) {
      const p = candidates[i];
      const hit = remaining.filter(r => p.x >= r.x1 && p.x <= r.x2 && p.y >= r.y1 && p.y <= r.y2).length;
      if (hit > bestHit) { bestHit = hit; bestIdx = i; }
    }
    if (bestHit === 0) break;
    const chosen = candidates.splice(bestIdx, 1)[0];
    net.push(chosen);
    remaining = remaining.filter(r => !(chosen.x >= r.x1 && chosen.x <= r.x2 && chosen.y >= r.y1 && chosen.y <= r.y2));
  }
  return net;
}

function draw(net, heavy, allRanges) {
  ctx.clearRect(0, 0, W, H);
  // draw all ranges; highlight heavy ones
  for (const r of allRanges) {
    const isHeavy = heavy.some(h => h.x1 === r.x1 && h.y1 === r.y1 && h.x2 === r.x2 && h.y2 === r.y2);
    ctx.strokeStyle = isHeavy ? '#457b9d' : '#cce0ed';
    ctx.lineWidth = isHeavy ? 1.4 : 0.8;
    ctx.fillStyle = isHeavy ? 'rgba(69,123,157,0.07)' : 'transparent';
    ctx.fillRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
    ctx.strokeRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
  }
  // draw universe points; net points are larger and red
  for (const p of universe) {
    const inNet = net.some(n => n.x === p.x && n.y === p.y);
    ctx.beginPath();
    ctx.arc(p.x, p.y, inNet ? 5.5 : 3.5, 0, Math.PI * 2);
    ctx.fillStyle = inNet ? '#e63946' : '#adb1b8';
    ctx.fill();
  }
}

let currentNet = [], currentHeavy = [], currentRanges = [];

function runBuild() {
  const eps = parseFloat(slider.value);
  currentRanges = buildRanges();
  currentHeavy = heavyRanges(currentRanges, eps);
  currentNet = buildNet(currentHeavy, eps);
  draw(currentNet, currentHeavy, currentRanges);
  const threshold = Math.ceil(eps * universe.length);
  // build status line
  statusEl.textContent = fmt('Net size: %length% points stab all %length2% heavy ranges (threshold ≥ %threshold% pts).', { length: currentNet.length, length2: currentHeavy.length, threshold: threshold });
  statusEl.className = 'status ok';
  console.log('epsilon', eps, '| net size:', currentNet.length, '| heavy ranges:', currentHeavy.length);
}

function resetDemo() {
  initUniverse();
  currentNet = []; currentHeavy = []; currentRanges = [];
  draw([], [], []);
  statusEl.textContent = 'Click Build ε-net to sample a net.';
  statusEl.className = 'status info';
}

slider.addEventListener('input', () => {
  epsVal.textContent = parseFloat(slider.value).toFixed(2);
});

document.getElementById('btn-build').addEventListener('click', runBuild);
document.getElementById('btn-reset').addEventListener('click', resetDemo);

// initialize on load — show blank canvas with points
initUniverse();
draw([], [], []);
statusEl.className = 'status info';

<!-- Epsilon-net demo: build a small net that stabs every heavy range -->
<div class="controls">
  <label for="eps-slider">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">Build ε-net</button>
  <button id="btn-reset" type="button" class="ghost">New universe</button>
</div>
<canvas id="canvas" width="440" height="300"></canvas>
<div id="status" class="status">Click Build ε-net to sample a net.</div>
<div class="legend">
  <span class="dot univ"></span> universe
  <span class="dot net"></span> net point
  <span class="box-samp"></span> heavy ranges
</div>

/* Demo styles — canvas-based epsilon-net visualizer */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Epsilon-net demo: random universe of points + axis-aligned rectangle ranges.
const W = 440, H = 300;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('eps-slider');
const epsVal = document.getElementById('eps-val');
const statusEl = document.getElementById('status');

// Universe of random points drawn uniformly on the canvas
const MARGIN = 20;
const N_PTS = 50;
let universe = [];

function randInt(lo, hi) { return Math.floor(Math.random() * (hi - lo + 1)) + lo; }

function initUniverse() {
  // generate N_PTS uniformly random points
  universe = [];
  for (let i = 0; i < N_PTS; i++) {
    universe.push({ x: randInt(MARGIN, W - MARGIN), y: randInt(MARGIN, H - MARGIN) });
  }
}

// Build a pool of random axis-aligned rectangle ranges
function buildRanges() {
  const ranges = [];
  // generate 40 random rectangles of varying sizes
  for (let i = 0; i < 40; i++) {
    const x1 = randInt(MARGIN, W - MARGIN - 40);
    const y1 = randInt(MARGIN, H - MARGIN - 30);
    const x2 = randInt(x1 + 20, Math.min(x1 + 180, W - MARGIN));
    const y2 = randInt(y1 + 15, Math.min(y1 + 130, H - MARGIN));
    ranges.push({ x1, y1, x2, y2 });
  }
  return ranges;
}

// A range is heavy if it contains >= eps * |universe| points
function heavyRanges(ranges, eps) {
  const threshold = eps * universe.length;
  return ranges.filter(r => {
    const inside = universe.filter(p => p.x >= r.x1 && p.x <= r.x2 && p.y >= r.y1 && p.y <= r.y2);
    return inside.length >= threshold;
  });
}

// Greedy set-cover net: pick the point that stabs the most remaining heavy ranges
// This always finds a valid net (every heavy range gets stabbed) though not the smallest.
function buildNet(heavyRangesList, eps) {
  const net = [];
  let remaining = [...heavyRangesList];
  const candidates = [...universe];
  // greedy: always add the point hitting the most uncovered heavy ranges
  while (remaining.length > 0 && candidates.length > 0) {
    let bestIdx = 0, bestHit = 0;
    for (let i = 0; i < candidates.length; i++) {
      const p = candidates[i];
      const hit = remaining.filter(r => p.x >= r.x1 && p.x <= r.x2 && p.y >= r.y1 && p.y <= r.y2).length;
      if (hit > bestHit) { bestHit = hit; bestIdx = i; }
    }
    if (bestHit === 0) break;
    const chosen = candidates.splice(bestIdx, 1)[0];
    net.push(chosen);
    remaining = remaining.filter(r => !(chosen.x >= r.x1 && chosen.x <= r.x2 && chosen.y >= r.y1 && chosen.y <= r.y2));
  }
  return net;
}

function draw(net, heavy, allRanges) {
  ctx.clearRect(0, 0, W, H);
  // draw all ranges; highlight heavy ones
  for (const r of allRanges) {
    const isHeavy = heavy.some(h => h.x1 === r.x1 && h.y1 === r.y1 && h.x2 === r.x2 && h.y2 === r.y2);
    ctx.strokeStyle = isHeavy ? '#457b9d' : '#cce0ed';
    ctx.lineWidth = isHeavy ? 1.4 : 0.8;
    ctx.fillStyle = isHeavy ? 'rgba(69,123,157,0.07)' : 'transparent';
    ctx.fillRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
    ctx.strokeRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
  }
  // draw universe points; net points are larger and red
  for (const p of universe) {
    const inNet = net.some(n => n.x === p.x && n.y === p.y);
    ctx.beginPath();
    ctx.arc(p.x, p.y, inNet ? 5.5 : 3.5, 0, Math.PI * 2);
    ctx.fillStyle = inNet ? '#e63946' : '#adb1b8';
    ctx.fill();
  }
}

let currentNet = [], currentHeavy = [], currentRanges = [];

function runBuild() {
  const eps = parseFloat(slider.value);
  currentRanges = buildRanges();
  currentHeavy = heavyRanges(currentRanges, eps);
  currentNet = buildNet(currentHeavy, eps);
  draw(currentNet, currentHeavy, currentRanges);
  const threshold = Math.ceil(eps * universe.length);
  // build status line
  statusEl.textContent = fmt('Net size: %length% points stab all %length2% heavy ranges (threshold ≥ %threshold% pts).', { length: currentNet.length, length2: currentHeavy.length, threshold: threshold });
  statusEl.className = 'status ok';
  console.log('epsilon', eps, '| net size:', currentNet.length, '| heavy ranges:', currentHeavy.length);
}

function resetDemo() {
  initUniverse();
  currentNet = []; currentHeavy = []; currentRanges = [];
  draw([], [], []);
  statusEl.textContent = 'Click Build ε-net to sample a net.';
  statusEl.className = 'status info';
}

slider.addEventListener('input', () => {
  epsVal.textContent = parseFloat(slider.value).toFixed(2);
});

document.getElementById('btn-build').addEventListener('click', runBuild);
document.getElementById('btn-reset').addEventListener('click', resetDemo);

// initialize on load — show blank canvas with points
initUniverse();
draw([], [], []);
statusEl.className = 'status info';

Result

Console

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 Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/epsilon-nets/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Why a small sample can represent an enormous set system