with $|X|\geq k$, find a $k$-clustering ${\mathcal{C}}_k$ of $X$ with minimal diameter cost.

For our analysis of agglomerative clustering, we repeatedly use the volume argument stated in Lemma \[volume\_lem\]. This argument provides an upper bound on the minimum distance between two points from a finite set of points lying inside the union of finitely many balls. For the application of this argument, the following definition is crucial.

Let $k\in{\mathbb{N}}$ and $r\in{\mathbb{R}}$. A set $X\subset{\mathbb{R}}^d$ is called *$(k,r)$-coverable* if there exist $y_1,\ldots,y_k\in{\mathbb{R}}^d$ with $X\subseteq\bigcup_{i=1}^k\operatorname{B}_r^d(y_i)$.

\[volume\_lem\] Let $k\in{\mathbb{N}}$, $r\in{\mathbb{R}}$ and $P\subset{\mathbb{R}}^d$ be finite and $(k,r)$-coverable with $|P|>k$. Then, there exist distinct $p,q\in P$ such that $\|p-q\|\leq4r\sqrt[d]{\frac{k}{|P|}}$.

Let $Z\subset{\mathbb{R}}^d$ with $|Z|=k$ and $P\subset\bigcup_{z\in Z}\operatorname{B}_r^d(z)$. We define $\delta$ to be the minimum distance between two points of $P$, i.e. $\delta:=\min_{\substack{p,q\in P\\p\neq q}}\|p-q\|$. We assume for contradiction that $u:=4r\sqrt[d]{\frac{k}{|P|}}<\delta$. Since $|P|>k$ there exists $z\in Z$ with $\left|\operatorname{B}_r^d(z)\cap P\right|\geq2$. It follows that $\delta\leq2r$ and hence, $\frac{u}{2}<r$. Note that for any $y\in{\mathbb{R}}^d$, $R\in{\mathbb{R}}$, and any norm $\|\cdot\|$, we have $\operatorname{vol}\left(\operatorname{B}_R^d(y)\right)=R^d\cdot V_d$, where $V_d$ is the volume of the $d$-dimensional unit ball $\operatorname{B}_1^d(0)$ (see [@webster], Corollary 6.2.15). Therefore, we deduce $$\operatorname{vol}\left(\bigcup_{z\in Z}\operatorname{B}_{r+\nicefrac{u}{2}}^d(z)\right)<\sum_{z\in Z}\operatorname{vol}\left(\operatorname{B}_{2r}^d(z)\right)\leq k\cdot(2r)^d\cdot V_d.$$ Furthermore, since any $p\in P$ is contained in a ball $\operatorname{B}_r^d(z)$ for some 