$z\in Z$, we conclude that any ball $\operatorname{B}_{\nicefrac{u}{2}}^d(p)$ for $p\in P$ is contained in a ball $\operatorname{B}_{r+\nicefrac{u}{2}}^d(z)$ for some $z\in Z$ (see Figure \[pre\_volem\_fig\]). Thus, we deduce $$\label{volume_lem_eq}
\operatorname{vol}\left(\bigcup_{p\in P}\operatorname{B}_{\nicefrac{u}{2}}^d(p)\right)<k\cdot(2r)^d\cdot V_d.$$ However, since $u<\delta$, for any distinct $p,q\in P$, we have $\operatorname{B}_{\nicefrac{u}{2}}^d(p)\cap\operatorname{B}_{\nicefrac{u}{2}}^d(q)=\varnothing$. Therefore, the total volume of the $|P|$ balls $\operatorname{B}_{\nicefrac{u}{2}}^d(p)$ is given by $$\operatorname{vol}\left(\bigcup_{p\in P}\operatorname{B}_{\nicefrac{u}{2}}^d(p)\right)=|P|\left(\frac{u}{2}\right)^dV_d=k\cdot(2r)^d\cdot V_d,$$ using the definition of $u$. This contradicts (\[volume\_lem\_eq\]). We obtain $\delta\leq u$, which proves the lemma.

(0,0)(100,45)

(100,0)[0.6]{} (20,20)[0.6]{} (20,20)[15]{} (101,-2)[$z$]{} (21,18)[$p$]{}

(100,0)[82.2]{}[147]{}[180]{} (100,0)[97.2]{}[152]{}[180]{}

(100,0)(29,41) (20,20)(8,29) (100,0)(3,3)

(61,25)[$r$]{} (53,4.5)[$r+\nicefrac{u}{2}$]{} (10,20)[$\nicefrac{u}{2}$]{}

Analysis {#analysis_sec}
========

In this section we analyze the agglomerative clustering algorithms for the (discrete) $k$-center problem and the diameter $k$-clustering problem. As mentioned in the introduction, an agglomerative algorithm takes a bottom-up approach. It starts with the $|X|$-clustering that contains one cluster for each input point and then successively merges two of the remaining clusters such that the cost of the resulting clustering is minimized. That is, in each merge step the agglomerative algorithms for Problem \[drad\_prob\], Problem \[rad\_prob\] and Problem \[diam\_prob\] minimize the discrete radius, the radius and the diameter of the resulting cluster, respectively.

Our main objective is the agglomerative complete linkage clustering algorithm, which minimizes the diameter in every 