clusters will be at least twice the number of these balls. It follows that there are many pairs of clusters that are contained in the same ball. Then, as long as the existence of at least one such pair can be guaranteed, the radius of the cluster created next can be bounded by the radius of the balls. The following lemma will be used to bound the increase of the cost during a single phase.

\[rad\_2k\_phaselem\] Let $m\in{\mathbb{N}}$ with $2k<m\leq|X|$. Then, $$\label{rad_2k_phaseeq}
\operatorname{cost_{rad}}\left({\mathcal{C}}_{\left\lfloor\frac{3m}{4}\right\rfloor}\right)<\left(1+6\sqrt[d]{\frac{2k}{m}}\right)\cdot\operatorname{cost_{rad}}({\mathcal{C}}_m)+6\sqrt[d]{\frac{2k}{m}}\cdot\operatorname{opt}_k.$$

Let ${\mathcal{P}}=\{P_1,\ldots,P_k\}$ be an optimal $k$-clustering of $X$. We fix $y_1,\ldots,y_k\in{\mathbb{R}}^d$ such that $P_i\subset\operatorname{B}_{\operatorname{opt}_k}(y_i)$ for $i=1,\ldots,k$. For any $C\in{\mathcal{C}}_m$ let $z_C\in{\mathbb{R}}^d$ such that $C\subset\operatorname{B}_{\operatorname{cost_{rad}}({\mathcal{C}}_m)}(z_C)$. It follows that each $z_C$ is contained in at least one of the balls $\operatorname{B}_{\operatorname{opt}_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)}(y_i)$ for $i=1,\ldots,k$ (see Figure \[rad\_2k\_phasefig1\]).

(0,0)(100,40)

(100,0)[0.6]{} (33,16)[0.6]{} (20,20)[0.6]{} (20,20)[15]{} (101,-2)[$y_i$]{} (21,18)[$z_C$]{}

(100,0)[70]{}[147]{}[180]{} (100,0)[84]{}[152]{}[180]{}

(100,0)(40,36) (20,20)(8,11) (100,0)(16,3)

(64,25)[$opt_k$]{} (60,4.5)[$opt_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)$]{} (-20,20)[$\operatorname{cost_{rad}}({\mathcal{C}}_m)$]{} (3,20)(13,16)

For $\lambda\in{\mathbb{R}}$ with $\lambda>0$ a ball of radius $\operatorname{opt}_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)$ can be covered by $\left\lceil\left(\frac{3}{\lambda}\right)^d\right\rceil$ balls of radius $\lambda\left(\operatorname{opt}_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)\right)$ (see [@naszodi]). Choosing $\lambda=\frac{3}{\sqrt[d]{\left\lfloor\frac{m}{2k}\right\rfloor}}$, we get that each of the balls $\operatorname{B}_{\operatorname{opt}_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)}(y_i)$ for $i=1,\ldots,k$ can be covered by $\ell:=\left\lfloor\frac{m}{2k}\right\rfloor\leq\frac{m}{2k}$ balls of radius $\varepsilon=\frac{3}{\sqrt[d]{\left\lfloor\frac{m}{2k}\right\rfloor}}\left(\operatorname{opt}_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)\right)$. Therefore, there exist $k\cdot\ell\leq\frac{m}{2}$ balls $B_1,\ldots,B_{k\ell}$ of radius $\varepsilon$ such that each $z_C$ for $C\in{\mathcal{C}}_m$ is 