$\epsilon$-net

DefinitionSuppose $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$-netfor $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.

TheoremSuppose $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)$ isthe 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\}$ isa 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 }$

ExampleIn $X={ℝ}^2$ with the usualCartesian 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.