1
$\begingroup$

Definition Doubling dimension ($\dim_D(M)=k$): A Metric space $M=(V,d)$ has doubling dimension at most $k$ if for any $x\in V$ & $r>0$, $B(x,r)\subseteq\bigcup^{2^k}_{i=1}B(x_i,r/2)$.

With this definition, a paper that i have read stated without proof $\dim_D(N)\leq2\dim_D(V)$ for any net $N\subseteq V$, where $N_\epsilon = \epsilon$-net means it is $\epsilon$-covering ($\forall v\in V, \exists n\in N_\epsilon$ s.t. $d(n,v)<\epsilon$) and $\epsilon$-separated (Take $n_1\neq n_2\in N_\epsilon$, $d(n_1,n_2)>\epsilon$)

I would like to know the reasoning for $\dim_D(N)\leq2\dim_D(V)$, many thanks. I have no idea how to construct $\dim_D(N)$ here.

$\endgroup$
3
  • $\begingroup$ What's the relation between $N$ and $N_\epsilon$? $\endgroup$ Commented Jan 15, 2016 at 8:17
  • $\begingroup$ THe title is quite misleading: not "half of" but "at most twice". $\endgroup$ Commented Jan 15, 2016 at 10:33
  • $\begingroup$ @JochenWengenroth $N\in\{N_\epsilon\}$ $\endgroup$
    – orb
    Commented Jan 15, 2016 at 12:27

1 Answer 1

0
$\begingroup$

This holds for every subset $N\subseteq V$, not only for nets.

Every ball $B(x,r)$ is covered by a union of $2^{2k}$ balls $B(x_i,r/4)$. Now, if for some $i$ there exists $n_i\in B(x_i,r/4)\cap N$, then $B(x_i,r/4)\subseteq B(n_i,r/2)$. So such balls $B(n_i,r/2)$ cover $B(x,r)\cap N$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .