the cluster created last. Furthermore, the discrete radius of the union of any two clusters is always an upper bound for the cost of the clustering to be computed next.

We prove Theorem \[drad\_result\] in two steps. First, Proposition \[drad\_2k\_prop\] in Section \[drad\_2k\_sec\] provides an upper bound to the cost of the intermediate $2k$-clustering. This upper bound is independent of $k$ and $|X|$, only linear in $d$ and may be of independent interest. In its proof, we use Lemma \[volume\_lem\] to bound the distance between the centers of pairs of remaining clusters. The cost of merging such a pair gives an upper bound to the cost of the next merge step. Therefore, we can bound the discrete radius of the created cluster by the sum of the larger of the two clusters’ discrete radii and the distance between their centers.

Second, in Section \[drad\_rem\_sec\], we analyze the remaining $k$ merge steps of Algorithm \[drad\_algo\] down to the computation of the $k$-clustering. There, we no longer need to apply the volume argument from Lemma \[volume\_lem\] to bound the distance between two cluster centers. It will be replaced by a very simple bound that is already sufficient. Analogously to the first step, 