A ball can be covered by N balls of radius epsilon*r

Given the Doubling Dimension D - a ball or radius r can be covered by smaller balls definition, we can apply it iteratively to break down ball of radius $r$ into smaller and smaller balls

Recursively cover each ball of radius $r$ with $2^D$ balls of half the radius $r/2$, then each of those with $2^D$ balls of radius $r/4$ and so on. After $k$ subdivisions, the radius of each ball becomes $r/2^k$ and the number of balls needed is $(2^D{)}^k$.

In terms of $ϵ$, we want to cover a ball of radius $r$ with smaller balls of radius $ϵr$, with $ϵ\le 1$. Set $ϵ=1/2^k$ so that $ϵr=r/2^k$. Solving for $k$, we get $k={\log }_2(1/ϵ)$.

Substituting $k={\log }_2(1/ϵ)$ on the number of balls we get:

$$2^{kD}=2^{D{\log }_2(1/ϵ)}=(\frac{1}{ϵ}{)}^D$$

Takeaway: a ball of radius $r$ can always be covered by at most $(1/ϵ{)}^D$ balls of radius $ϵr$.

See also

• Doubling Dimension D - a ball or radius r can be covered by smaller balls — the definition this construction is built on; iterative covering is the proof technique that extracts the $(1/ϵ{)}^D$ bound
• Coreset is a small subset from P which represent P well — the $(1/ϵ{)}^D$ bound directly controls coreset size: the number of centers selected per shard in the MapReduce algorithm is bounded by this quantity
• Linear Recursion is a chain of deferred operations — iterative halving is a recursive process: the covering of radius $r$ is defined in terms of the covering of radius $r/2$, with depth ${\log }_2(1/ϵ)$

References

• @ceccarelloSolving$k$centerClustering2021