contained in at least one of these balls. For $i=1,\ldots,k\ell$ let $a_i\in{\mathbb{R}}^d$ such that $B_i=\operatorname{B}_\varepsilon(a_i)$. Then, any cluster $C\in{\mathcal{C}}_m$ is contained in at least one of the balls $A_1,\ldots,A_{k\ell}$ with $A_i=\operatorname{B}_{\operatorname{cost_{rad}}({\mathcal{C}}_m)+\varepsilon}(a_i)$ for $i=1,\ldots,k\ell$ (see Figure \[rad\_2k\_phasefig2\]).

(-30,0)(120,50)

(45,5)[45]{}[-7]{}[187]{}

(45,5)[30]{}[-10]{}[190]{} (45,5)[0.6]{} (42,2)[$a_i$]{} (45,5)(75,8) (58,3)[$\varepsilon$]{} (45,5)(30,47) (33,42)[$\operatorname{cost_{rad}}({\mathcal{C}}_m)+\varepsilon$]{}

(20,15)[0.6]{} (20,15)[15]{} (20,15)(8,24) (21,13)[$z_{C_1}$]{} (-2,15)(13,19) (-25,13)[$\operatorname{cost_{rad}}({\mathcal{C}}_m)$]{}

(60,25)[0.6]{} (60,25)[15]{} (61,23)[$z_{C_2}$]{}

(60,-40)[70]{}[45]{}[145]{} (79,0)(90,23) (82,3)[$opt_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)$]{}

Let $t:=\left\lfloor\frac{3m}{4}\right\rfloor$ and ${\mathcal{C}}_m\cap {\mathcal{C}}_{t+1}$ be the set of clusters from ${\mathcal{C}}_m$ that still exist $\left\lceil\frac{m}{4}\right\rceil-1$ merge steps after the computation of ${\mathcal{C}}_m$. In each iteration of its loop, the algorithm can merge at most two clusters from ${\mathcal{C}}_m$. Thus, $|{\mathcal{C}}_m\cap {\mathcal{C}}_{t+1}|>\frac{m}{2}$.

Since $k\ell\leq\frac{m}{2}$, there exist two clusters $C_1,C_2\in{\mathcal{C}}_m\cap {\mathcal{C}}_{t+1}$ that are contained in the same ball $A_i$ with $i\in\{1,\ldots,k\ell\}$. Therefore, merging clusters $C_1$ and $C_2$ would result in a cluster whose radius can be upper bounded by $\operatorname{rad}(C_1\cup C_2)\leq\operatorname{cost_{rad}}({\mathcal{C}}_m)+\varepsilon$. Using Observation \[rad\_greedy\_obs\] and the fact that $C_1$ and $C_2$ are part of the clustering ${\mathcal{C}}_{t+1}$, we can upper bound the cost of ${\mathcal{C}}_t$ by $$\operatorname{cost_{rad}}({\mathcal{C}}_t)\leq\operatorname{cost_{rad}}({\mathcal{C}}_m)+\varepsilon.$$

It remains to show $\varepsilon<6\sqrt[d]{\frac{2k}{m}}\cdot\bigl(\operatorname{opt}_k+\operatorname{cost_{rad}}({\mathcal{C}}_m)\bigr)$. Since $\frac{m}{2k}>1$, we have $\frac{m}{2k}<2\left\lfloor\frac{m}{2k}\right\rfloor$. Thus, $\sqrt[d]{\frac{m}{2k}}<\sqrt[d]{2\left\lfloor\frac{m}{2k}\right\rfloor}\leq2\sqrt[d]{\left\lfloor\frac{m}{2k}\right\rfloor}$ and $\frac{3}{\sqrt[d]{\left\lfloor\frac{m}{2k}\right\rfloor}}<6\sqrt[d]{\frac{2k}{m}}$.

To prove Proposition \[rad\_2k\_prop\], we apply Lemma \[rad\_2k\_phaselem\] for $\left\lceil\log_\frac{4}{3}\frac{|X|}{2k}\right\rceil$ consecutive phases.

Let $u:=\left\lceil\log_\frac{4}{3}\frac{|X|}{2k}\right\rceil$ and define $m_i:=\left\lceil\left(\frac{3}{4}\right)^i|X|\right\rceil$ for all $i=0,\ldots,u$. Then, $m_u\leq2k$ and 