# Minimal number of balls in a cover of a compact set

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.

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\|

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.

• Thank you, this is a very nice solution! By the way, I guess you meant to write $B_i$ instead of $U_i$. May 24, 2020 at 18:00
• Ah yes, you should treat these as the same thing May 24, 2020 at 18:01