$\varepsilon$-net

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

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

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

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

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

Proof. Suppose $N$ is an $\varepsilon$-net for $S$. If $x\in S$, there is an $y\in N$ such that $x\in B_{\varepsilon}(y)$. Thus, $x$ is covered by some set in $\{B_{\varepsilon}(x)\mid x\in N\}$. Conversely, suppose $\{B_{\varepsilon}(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_{\varepsilon}(y)$. Hence $d(x,y)<\varepsilon$ with $y\in N$. $\Box$

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

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

is an $\varepsilon$-net for $X$ assuming that $\varepsilon>\sqrt{2}/2$. $\Box$

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

References

Title $\varepsilon$-net varepsilonnet 2013-03-22 13:37:54 2013-03-22 13:37:54 Koro (127) Koro (127) 4 Koro (127) Definition msc 54E35 Cover