ε-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 the ε-net 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. In fact, any (axis-parallel) square, regardless of size, will have a similar 8-point 1/4-net.

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, suppose we wish to estimate the area of a given region P that falls inside a particular rectangle. One can estimate this area to within an additive factor of ɛ times the area of P by first finding an ɛ-net of P, counting the proportion of elements in the ɛ-net falling inside the rectangle, and then multiplying by the area of P. The runtime of the algorithm depends only on ɛ and not P. One straightforward way to compute an ɛ-net with high probability is to take a sufficient number of random points, where the number of random points also depends only on ɛ. ɛ-nets also provide approximation algorithms for the hitting set and set cover problems.

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.