following, *cost* always means radius cost and $\operatorname{opt}_k$ refers to the cost of an optimal $k$-center clustering of $X\subset{\mathbb{R}}^d$ where $k\in{\mathbb{N}}$ with $k\leq|X|$.

\[rad\_greedy\_obs\] The cost of all computed clusterings is equal to the radius of the cluster created last. Furthermore, the radius of the union of any two clusters is always an upper bound for the cost of the clustering to be computed next.

The following theorem states our result for the $k$-center problem.

\[rad\_result\] Let $X\subset{\mathbb{R}}^d$ be a finite set of points. Then, for all $k\in{\mathbb{N}}$ with $k\leq|X|$, the partition ${\mathcal{C}}_k$ of $X$ into $k$ clusters as computed by Algorithm \[rad\_algo\] satisfies $$\operatorname{cost_{rad}}({\mathcal{C}}_k)=O(\log k)\cdot\operatorname{opt}_k,$$ where $\operatorname{opt}_k$ denotes the cost of an optimal solution to Problem \[rad\_prob\], and the constant hidden in the $O$-notation is singly exponential in the dimension $d$.

Theorem \[rad\_result\] holds for any particular tie-breaking strategy. However, to keep the analysis simple, we assume that there are no ties. That is, we assume that for any input set $X$ the clusterings computed by Algorithm \[rad\_algo\] are uniquely determined. As in the proof of Theorem \[drad\_result\], we first show a bound for the cost of the intermediate $2k$-clustering. However, we have to apply a different analysis. As 