1
$\begingroup$

Let $X$ be the unit ball of $(\mathbb{R}^n,\|\cdot\|_2)$. A finite set $N=N(\varepsilon)$ is a $\varepsilon$-net of $X$ if every point in $X$ is at most a distance $\varepsilon$ from a point from $N$.

It is well-known that $N(\varepsilon)=(O(1)/\varepsilon)^n$ as $\varepsilon\rightarrow 0$. My question is whether there exists a function $\varepsilon(n)$ such that for all $\varepsilon>\varepsilon(n)$ there exists a $\varepsilon$-net of size $1/\varepsilon^2$ (or some other dimension-free quantity). Of course, this question only becomes interesting when $\varepsilon(n)<1$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Since the balls of radius $\epsilon$ centered at points of any $\epsilon$-net $N$ cover $X$, by volume comparison we have $\operatorname{card}(N )\ge\epsilon^{-n}$. If $\operatorname{card}N\le1/\epsilon^2$ it is needed $\epsilon^{n-2}\ge1$, so there should be no $\epsilon(n)<1$ as you want if $n>2$. $\endgroup$
    – Pietro Majer
    Commented Oct 25, 2013 at 22:29
  • $\begingroup$ Thanks! That is neat. I am new to this, so I don't know how to declare this as an answer. I apologize. $\endgroup$
    – Cristóbal Guzmán
    Commented Oct 29, 2013 at 21:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .