ε-net

An $\varepsilon$-net describes several related concepts in mathematics.

Probability theory

Let $P$ be a probability distribution over some set $X$. An $\varepsilon$-net for a class $H\subseteq 2^{X}$ of subsets of $X$ is any subset $S\subseteq X$ such that for any $h\in H$

$P(h)\geq \varepsilon \quad \Longrightarrow \quad S\cap h\neq \varnothing .$

Intuitively $S$ approximates the probability distribution.

A stronger notion is $\varepsilon$-approximation. An $\varepsilon$-approximation for class $H$ is subset $S\subseteq X$ such that for any $h\in H$ it holds

$\left|P(h)-{\frac {|S\cap h|}{|S|}}\right|<\varepsilon$

Computational geometry

An ε-net with ε=1/4 of the unit square in the range space where the ranges are closed filled rectangles.

Let X be a set and R be a set of subsets of X; such a pair is called a range space or hypergraph, and the elements of R are called ranges or hyperedges. An ε-net of a subset P of X is a subset N of P such that any range r ∈ R with |r ∩ P| ≥ ε|P| intersects N. In other words, any range that intersects at least a proportion ε of the elements of P must also intersect N.

For example, suppose X is the set of points in the two-dimensional plane, R is the set of closed filled rectangles (products of closed intervals), and P is the unit square [0,1] × [0,1]. Then the set R consisting of the 8 points shown in the diagram to the right is a 1/4-net of P, because any closed filled rectangle intersecting at least 1/4 of the unit square must intersect one of these points.

For any range space with finite VC dimension d, regardless of the choice of P and ɛ, there exists an ɛ-net of P of size $O\left({\frac {d}{\epsilon }}\log {\frac {d}{\epsilon }}\right)$; because the size of this set is independent of P, any set P can be described using a set of fixed size.

This facilitates the development of efficient approximation algorithms. For example, consider the range space where the ranges are half-planes. Given a half-plane, one can estimate the number of elements of P falling on one side of the half plane within any desired approximation ratio ɛ by first finding an ɛ-net of P, counting the number of elements in the ɛ-net falling on one side of the half plane, and then multiplying by |P|. The runtime of the algorithm depends only on ɛ and not |P|.

Set theory

In set theory, an ɛ-net is a set of points in a metric space such that each point of the space is within distance ɛ of some point in the set. For example, the integers are an ɛ-net of the real numbers for any ɛ > 0.5.

This should not be confused with the concept of a net, which is equivalent to a sequence in a metric space.