step. Nevertheless, we start with the analysis of the agglomerative algorithm for the discrete $k$-center problem since it is the simplest one of the three. Then we adapt our analysis to the $k$-center problem and finally to the diameter $k$-clustering problem. In each case we need to introduce further techniques to deal with the increased complexity of the given problem.

We show that all three algorithms compute an $O(\log k)$-approximation for the particular corresponding clustering problem. However, the dependency on the dimension which is hidden in the $O$-notation ranges from only linear and additive in case of the discrete $k$-center problem to a factor that is doubly exponential in case of the diameter $k$-clustering problem.

As mentioned in the introduction, the cost of optimal solutions to the three problems are within a factor of $2$ from each other. That is, each algorithm computes an $O(\log k)$-approximation for all three problems. However, we will analyze the proper agglomerative algorithm for each problem.

Discrete $k$-center clustering {#drad_sec}
------------------------------

The agglomerative algorithm for the discrete $k$-center problem is stated as Algorithm \[drad\_algo\].

------------------------------------------------------------------------

<span style="font-variant:small-caps;">AgglomerativeDiscreteRadius</span>$(X)$:\

  ----- --------------------------------------------------
    $X$ finite set of input points from ${\mathbb{R}}^d$
  ----- --------------------------------------------------

  : The agglomerative algorithm for the 