conclude that merging $C_1$ and $C_2$ would result in a cluster whose discrete radius can be upper bounded by $\operatorname{drad}(C_1\cup C_2)<\operatorname{cost_{drad}}({\mathcal{C}}_m)+4\sqrt[d]{\frac{2k}{m}}\cdot\operatorname{opt}_k$ (see Figure \[drad\_merge\_fig\]). The result follows using $C_1,C_2\in{\mathcal{C}}_{t+1}$ and Observation \[drad\_greedy\_obs\].

(0,0)(100,45)

(20,20)[0.6]{} (80,25)[0.6]{} (20,20)[20]{} (80,25)[20]{} (15,17)[$p_{C_1}$]{} (81,23)[$p_{C_2}$]{}

(20,20)[80]{}[-15]{}[20]{} (20,20)(99,10)

(20,20)(2,29) (80,25)(98,34) (20,20)(80,25)

(8,27)[$\operatorname{cost_{drad}}({\mathcal{C}}_m)$]{} (69,33)[$\operatorname{cost_{drad}}({\mathcal{C}}_m)$]{}

To prove Proposition \[drad\_2k\_prop\], we apply Lemma \[drad\_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 $m_i>2k$ for all $i=0,\ldots,u-1$. Since $\left\lfloor\frac{3m_i}{4}\right\rfloor=\left\lfloor\frac{3}{4}\left\lceil\left(\frac{3}{4}\right)^i|X|\right\rceil\right\rfloor\leq\left\lfloor\left(\frac{3}{4}\right)^{i+1}|X|+\frac{3}{4}\right\rfloor\leq\left\lceil\left(\frac{3}{4}\right)^{i+1}|X|\right\rceil=m_{i+1}$ and Algorithm \[drad\_algo\] uses a greedy strategy, we get $\operatorname{cost_{drad}}({\mathcal{C}}_{m_{i+1}})\leq\operatorname{cost_{drad}}({\mathcal{C}}_{\left\lfloor\frac{3m_i}{4}\right\rfloor})$ for all $i=0,\ldots,u-1$. Combining this with Lemma \[drad\_2k\_phaselem\] (applied to $m=m_i$), we obtain $$\operatorname{cost_{drad}}({\mathcal{C}}_{m_{i+1}})<\operatorname{cost_{drad}}({\mathcal{C}}_{m_i})+4\sqrt[d]{\frac{2k}{m_i}}\cdot\operatorname{opt}_k.$$ By repeatedly applying this inequality for $i=0,\ldots,u-1$ and using $\operatorname{cost_{drad}}({\mathcal{C}}_{2k})\leq\operatorname{cost_{drad}}({\mathcal{C}}_{m_u})$ and $\operatorname{cost_{drad}}({\mathcal{C}}_{m_0})=0$, we deduce $$\operatorname{cost_{drad}}\left({\mathcal{C}}_{2k}\right)<\sum_{i=0}^{u-1}\left(4\sqrt[d]{\frac{2k}{m_i}}\cdot\operatorname{opt}_k\right)<4\sqrt[d]{\frac{2k}{|X|}}\cdot\sum_{i=0}^{u-1}\sqrt[d]{\left(\frac{4}{3}\right)^i}\cdot\operatorname{opt}_k.$$ Solving the geometric series and using $u-1<\log_\frac{4}{3}\frac{|X|}{2k}$ leads to $$\label{drad_gseq}
\operatorname{cost_{drad}}\left({\mathcal{C}}_{2k}\right)<4\sqrt[d]{\frac{2k}{|X|}}\cdot\frac{\sqrt[d]{\left(\frac{4}{3}\right)^u}-1}{\sqrt[d]{\frac{4}{3}}-1}\cdot\operatorname{opt}_k<\frac{4\sqrt[d]{\frac{4}{3}}}{\sqrt[d]{\frac{4}{3}}-1}\cdot\operatorname{opt}_k.$$ By taking only the first two terms of the series expansion of the exponential function, we get $\sqrt[d]{\frac{4}{3}}=e^{\frac{\ln\frac{4}{3}}{d}}>1+\frac{\ln\frac{4}{3}}{d}$. Substituting this bound into (\[drad\_gseq\]) gives $$\operatorname{cost_{drad}}\left({\mathcal{C}}_{2k}\right)<\frac{4\sqrt[d]{\frac{4}{3}}}{\ln\frac{4}{3}}d\cdot\operatorname{opt}_k<20d\cdot\operatorname{opt}_k.$$

### Analysis of the remaining merge steps {#drad_rem_sec}

The analysis of the remaining merge steps introduces the $O(\log k)$ term to the approximation factor of our result. It is similar to the analysis used in the proof of Proposition \[drad\_2k\_prop\]. Again, we divide the merge steps into phases. However, this 