this leads to a bound for the cost of merging a pair of clusters.

### Analysis of the $2k$-clustering {#drad_2k_sec}

\[drad\_2k\_prop\] Let $X\subset{\mathbb{R}}^d$ be finite. Then, for all $k\in{\mathbb{N}}$ with $2k\leq|X|$, the partition ${\mathcal{C}}_{2k}$ of $X$ into $2k$ clusters as computed by Algorithm \[drad\_algo\] satisfies $$\operatorname{cost_{drad}}({\mathcal{C}}_{2k})<20d\cdot\operatorname{opt}_k,$$ where $\operatorname{opt}_k$ denotes the cost of an optimal solution to Problem \[drad\_prob\].

To prove Proposition \[drad\_2k\_sec\], we divide the merge steps of Algorithm \[drad\_algo\] into phases, each reducing the number of remaining clusters by one fourth. The following lemma bounds the increase of the cost during a single phase by an additive term.

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

Let $R:=\operatorname{cost_{drad}}({\mathcal{C}}_m)$. From every cluster $C\in{\mathcal{C}}_m$, we fix a center $p_C\in C$ with $C\subset\operatorname{B}_R^d(p_C)$.

Let $t:=\left\lfloor\frac{3m}{4}\right\rfloor$. Then, ${\mathcal{C}}_m\cap{\mathcal{C}}_{t+1}$ is 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}$.

Let $P:=\{p_C{\,\vline~}C\in C_m\cap {\mathcal{C}}_{t+1}\}$. Then, $|P|=|{\mathcal{C}}_m\cap{\mathcal{C}}_{t+1}|>\frac{m}{2}>k$. Since $X$ is $(k,\operatorname{opt}_k)$-coverable, so is $P\subset X$. Therefore, by Lemma \[volume\_lem\], there exist distinct $C_1,C_2\in{\mathcal{C}}_m\cap{\mathcal{C}}_{t+1}$ such that $\|p_{C_1}-p_{C_2}\|\leq4\sqrt[d]{\frac{2k}{m}}\cdot\operatorname{opt}_k$. Then, the distance from $p_{C_1}$ to any $q\in C_2$ is at most $4\sqrt[d]{\frac{2k}{m}}\cdot\operatorname{opt}_k+R$. We 