$\epsilon$-net

Definition Suppose $X$ is a metric space with a metric $d$, and suppose $S$ is a subset of $X$. Let $\epsilon$ be a positive real number. A subset $N\subset S$ is an $\epsilon$-net for $S$ if, for all $x\in S$, there is an $y\in N$, such that .

For any $\epsilon >0$ and $S\subset X$, the set $S$ is trivially an $\epsilon$-net for itself.

Theorem Suppose $X$ is a metric space with a metric $d$, and suppose $S$ is a subset of $X$. Let $\epsilon$ be a positive real number. Then $N$ is an $\epsilon$-net for $S$, if and only if

$$\{B_{\epsilon }(y)\mid y\in N\}$$

is a cover for $S$. (Here $B_{\epsilon }(x)$ is the open ball with center $x$ and radius $\epsilon$.)

Proof. Suppose $N$ is an $\epsilon$-net for $S$. If $x\in S$, there is an $y\in N$ such that $x\in B_{\epsilon }(y)$. Thus, $x$ is covered by some set in $\{B_{\epsilon }(x)\mid x\in N\}$. Conversely, suppose $\{B_{\epsilon }(y)\mid y\in N\}$ is a cover for $S$, and suppose $x\in S$. By assumption, there is an $y\in N$, such that $x\in B_{\epsilon }(y)$. Hence with $y\in N$. $\mathrm{\square }$

Example In $X={ℝ}^2$ with the usual Cartesian metric, the set

$$N=\{(a,b)\mid a,b\in \mathbb{Z}Ã\mathrm{‚}Â\mathrm{ }\}$$

is an $\epsilon$-net for $X$ assuming that $\epsilon >\sqrt{2}/2$. $\mathrm{\square }$

The above definition and example can be found in [1], page 64-65.

Title	$\epsilon$-net
Canonical name	varepsilonnet
Date of creation	2013-03-22 13:37:54
Last modified on	2013-03-22 13:37:54
Owner	Koro (127)
Last modified by	Koro (127)
Numerical id	4
Author	Koro (127)
Entry type	Definition
Classification	msc 54E35
Related topic	Cover