The Vitali Covering Lemma

Setup

Let $\mathcal{F}$ be a finite collection of balls in $\mathbb{R}^d$. We want to find a disjoint subcollection $\mathcal{S} \subset \mathcal{F}$ such that

where $3B$ denotes the ball with the same center as $B$ but three times the radius.

The Greedy Algorithm

The proof is constructive:

1. Pick $B_1 \in \mathcal{F}$ with largest radius.
2. Remove all balls intersecting $B_1$.
3. Pick $B_2$ with largest radius among remaining balls.
4. Repeat until $\mathcal{F}$ is empty.

Why Factor 3?

If $B \in \mathcal{F}$ was removed because it intersects $B_i$, then:

since $B_i$ was chosen to have largest radius. Any point $x \in B$ satisfies:

hence $B \subset 3B_i$. $\blacksquare$