Bound on the covering number of a closed ball

455 Views Asked by At

Given a closed unit ball in $\mathbb{R}^{p}$, $\Gamma := \left\{ \theta \in \mathbb{R}^{p}: |\theta| \leq 1 \right\}$ with $|.|$ denoting the Euclidean norm, I would like to cover it with $k$ disjoint sets of diameter at most $\delta$, which are not necessarily open. Is it possible to say something about the magnitude of this number $k(\delta)$? The paper I am reading says that

$$ k\leq \left( 2 \sqrt{p}/\delta + 1\right)^{p}, $$

but it's not obvious to me how this bound comes to be. If anyone sees it, could I please ask to share his/her wisdom?

1

There are 1 best solutions below

1
On BEST ANSWER

Divide the box $[-1,1]^p$ into small boxes each of side at most $\delta/\sqrt{p}$. Each of them has diameter (diagonal) at most $\delta$ and you have something like $\lceil 2\sqrt{p}/\delta\rceil^p$ of them.