Minimal number of balls in a cover of a compact set

Question

Let $K \subseteq \mathbb R^n$ be compact.

Let $r>0$. Can we cover $K$ by $N(r)$ balls of radius $r$, centered around points that belong to $K$, with $N(r) \le c \frac{1}{\text{Vol}(B(r))}$?

Here $\text{Vol}(B(r))$ is the volume of an Eucldean ball of radius $r$ in $\mathbb R^n$; I want $c$ to be a constant which may depend on $K$ and on $n$, but not on $r$.

This upper bound cannot be lowered-since if $K=\cup_{i=1}^N B_i$, where all the $B_i$ are of radius $r$, then $$ \text{Vol}(K)\le \sum_{i=1}^N {\text{Vol}(B_i)}=N\text{Vol}(B(r)). $$

Here $\text{Vol}(K)$ refers to the Lebesgue measure of $K$.

I think that we can always cover $K$ by $\sim c \frac{1}{\text{Vol}(B(r))}$ balls if we don't care whether their centers lie in $K$: Just take a cube which contains $K$-and divide it into identical subcubes by putting a grid-now I guess we can replace the cubes with suitable balls and everything will be fine.

What if we insist to use only balls centered at points that belong to $K$? Since $K$ can be arbitrarily complicated, I am not sure how to adapt this scheme.

I tried googling various terms related to "bounds on the covering number", but failed to find an answer.

Answer 1

This is, in fact, quite simple.

First I'll define the two quantities you mention above. Given $K\subset \mathbb R^n$ as above and $r>0$, let

$$N(r) = \min\left\{N\in \mathbb N\ \bigg|\ K \subset \bigcup_{i=1}^N B_i,: B_i\text{ balls of radius r, centred at points }c_i \in K\right\},$$

and let $ N'(r) $ be the same quantity without requiring the centres to lie in $K$:

$$N'(r) = \min\left\{N\in \mathbb N\ \bigg|\ K \subset \bigcup_{i=1}^N B_i,: B_i\text{ balls of radius r in }\mathbb R^n\right\}.$$

Then we have a very simple claim, which you can combine with your estimate.

Claim. For all $r> 0$, $$N(r) \leq N'(r/2).$$

Proof. Given $r$, consider some minimal cover which obtains $N'(r/2)$:

$$\displaystyle K \subset \bigcup_{i=1}^{N'(r/2)} B_i,$$

where the $B_i$ are balls of radius $r/2$ whose centres needn't lie in $K$.

Then, since the cover is minimal, each $B_i$ must meet $K$, i.e. for each $i$ there is some point $x_i \in B_i\cap K$.

Now, since the distance from $x_i$ to the centre of $B_i$ is less than $r/2$ (as $x_i \in B_i$), every point in $B_i$ is less than $r$ away from $x_i$ (via triangle inequality if you like).

This gives the inclusion

$$ B_i \subset \mathbb B(x_i,r) := \{y \in \mathbb R^n : \|x - y\|<r\};$$

and consequently,

$$ K \subset \bigcup_{i=1}^{N'(r/2)} B_i \subset \bigcup_{i=1}^{N'(r/2)} \mathbb B(x_i,r) $$

so this gives you a cover of $K$ by $N'(r/2)$ balls of radius $r$, centred at points in $K$.

As for things to Google, this question is reminiscent of the Box Counting dimension.