# New bounds on the cohesion of complete-link and other linkage methods for
agglomeration clustering

Sanjoy Dasgupta
<EMAIL_ADDRESS>
University of California San Diego
&Eduardo S. Laber
<EMAIL_ADDRESS>
PUC-RIO

###### Abstract

Linkage methods are among the most popular algorithms for hierarchical
clustering. Despite their relevance the current knowledge regarding the
quality of the clustering produced by these methods is limited. Here, we
improve the currently available bounds on the maximum diameter of the
clustering obtained by complete-linkage for metric spaces.

One of our new bounds, in contrast to the existing ones, allows us to separate
complete-linkage from single-linkage in terms of approximation for the
diameter, which corroborates the common perception that the former is more
suitable than the latter when the goal is producing compact clusters.

We also show that our techniques can be employed to derive upper bounds on the
cohesion of a class of linkage methods that includes the quite popular
average-linkage.

##  1 Introduction

Clustering is the problem of partitioning a set of items so that similar items
are grouped together and dissimilar items are separated. It is a fundamental
tool in machine learning that is commonly used for exploratory analysis and
for reducing the computational resources required to handle large datasets.
For comprehensive descriptions of different clustering methods and their
applications, we refer to (Jain et al., 1999; Hennig et al., 2015).

One important type of clustering is hierarchical clustering. Given a set of
$n$ points, a hierarchical clustering is a sequence of clusterings $({\cal
C}^{0},{\cal C}^{1},\ldots,\mathcal{C}^{n-1})$, where ${\cal C}^{0}$ is a
clustering with $n$ unitary clusters, each of them corresponding to one of the
$n$ points, and ${\cal C}^{i}$, for $i\geq 1$, is obtained from ${\cal
C}^{i-1}$ by replacing two clusters of ${\cal C}^{i-1}$ with their union.
Hierarchical clustering algorithms are implemented in widely used machine
learning libraries such as scipy and they have applications in many contexts
such as in the study of evolution through phylogenetic trees (Eisen et al.,
1998).

There is a significant literature on hierarchical clustering; for good surveys
we refer to (Murtagh, 1983; Murtagh & Contreras, 2012). With regards to more
theoretical work, one important line of research consists of designing
algorithms for hierarchical clustering with provable guarantees for natural
optimization criteria such as cluster diameter and the sum of quadratic errors
(Dasgupta & Long, 2005; Charikar et al., 2004; Lin et al., 2010; Arutyunova &
Röglin, 2022). Another relevant line aims to understand the theoretical
properties (e.g. approximation guarantees) of algorithms widely used in
practice, such as linkage methods (Dasgupta & Long, 2005; Ackermann et al.,
2010; Großwendt & Röglin, 2015; Arutyunova et al., 2021; Großwendt et al.,
2019).

Here, we contribute to this second line of research by giving new and improved
analysis for the complete-linkage (Ackerman & Ben-David, 2016) and also for a
class of linkage methods that includes average-linkage (Ackerman & Ben-David,
2016) and minimax (Bien & Tibshirani, 2011).

###  1.1 Our Results

Let $({\cal X},dist)$ be a metric space, where ${\cal X}$ is a set of $n$
points. The diameter ${\tt diam}(S)$ of a set of points $S$ is given by ${\tt
diam}(S)=\max\\{dist(x,y)|x,y\in S\\}$. A _$k$ -clustering_
$\mathcal{C}=\\{C_{i}|1\leq i\leq k\\}$ is a partition of ${\cal X}$ into $k$
groups. We define

${\tt max\mbox{-}diam}(\mathcal{C}):=\max\\{{\tt diam}(C_{i})|1\leq i\leq
k\\}\,\,\mbox{ and }\,\,{\tt
avg\mbox{-}diam}(\mathcal{C}):=\frac{1}{k}\sum_{i=1}^{k}{\tt diam}(C_{i}).$

Moreover, let OPT${}_{{\tt DM}}(k)$ and OPT${}_{{\tt AV}}(k)$ be,
respectively, the minimum possible max-diam and avg-diam of a $k$-clustering
for $({\cal X},dist)$.

Arbitrary $k$. First, in Section 3, we prove that for all $k$ the maximum
diameter of the $k$-clustering produced by complete-linkage is at most
$k^{1.59}\textrm{OPT${}_{{\tt AV}}(k)$}$. Since $\textrm{OPT${}_{{\tt
AV}}(k)$}\leq\textrm{OPT${}_{{\tt DM}}(k)$}$, our result is an improvement
over $O(k^{1.59}\textrm{OPT${}_{{\tt DM}}(k)$})$, the best known upper bound
on the maximum diameter of complete-linkage (Arutyunova et al., 2023). Indeed,
our bound can improve the previous one by up to a factor of $k$ since there
are instances in which OPT${}_{{\tt AV}}(k)$ is
$\Theta(\frac{\textrm{OPT${}_{{\tt DM}}(k)$}}{k})$.

It is noteworthy that by using OPTAV rather than OPTDM, we can corroborate
with the intuition that complete-linkage produces clusters with smaller
diameters than those produced by single-linkage since, in addition to the
$k^{1.59}\textrm{OPT${}_{{\tt AV}}(k)$}$ upper bound for the former, we show
an instance in which the maximum diameter of the latter is
$\Omega(k^{2}\textrm{OPT${}_{{\tt AV}}(k)$})$. When OPTDM is employed,
unexpectedly, as pointed out in (Arutyunova et al., 2023), this separation is
not possible since the maximum diameter of complete-linkage is
$\Omega(k\textrm{OPT${}_{{\tt DM}}(k)$})$ while that of single-linkage is
$\Theta(k\textrm{OPT${}_{{\tt DM}}(k)$})$.

To obtain the aforementioned upper bound, our main technique consists of
carefully defining a partition of the clusters built by complete-linkage along
its execution and then bounding the diameter of the families in the partition.
This technique yields an arguably simpler analysis than that of (Arutyunova et
al., 2021, 2023).

Next, in Section 4, by using our technique in a significantly more involved
way, we show that the maximum diameter of the $k$-clustering produced by
complete-linkage is at most $(2k-2)\textrm{OPT${}_{{\tt DM}}(k)$}$ for $k\leq
4$ and at most $k^{1.30}\textrm{OPT${}_{{\tt DM}}(k)$},$ for $k>4$. Thus, we
considerably narrow the gap between the current upper bound and
$\Omega(k\textrm{OPT${}_{{\tt DM}}(k)$}),$ the best known lower bound.

Finally, in Section 5, we show that our techniques can be employed to obtain
upper bounds on cohesion criteria of the clustering built by methods that
belong to a class of linkage methods that includes average-linkage and
minimax. In particular, we show that the average pairwise distance of every
cluster in the $k$-clustering produced by average-linkage is at most
$k^{1,59}\textrm{OPT${}_{{\tt AV}}(k)$}$. To the best of our knowledge, our
analysis of the average-linkage is the first one regarding to a cohesion
criterion.

Low values of $k$ and practical applications. For large $k$, the upper bounds
of complete-linkage, though close to the lower bound, are high and, thus, are
not informative in the context of practical applications. However, as argued
below, we have a different scenario for the very relevant case in which $k$ is
small. The relevance of small $k$ is that, in general, people have
difficulties in analyzing a partition containing many groups (large $k$).

(Charikar et al., 2004; Dasgupta & Long, 2005) propose algorithms that obtain
a hierarchical clustering that guarantees an 8-approximation to the diameter
for every $k$. The analysis from (Arutyunova et al., 2023) give, respectively,
the following upper bounds on the approximation factor of single-linkage and
complete-linkage regarding the diameter: $4$ and $3$ for $k=2$; $6$ and
$5.71$, for $k=3$ and $8$ and $9$ for $k=4$. Our analysis gives an
approximation factor of $2k-2$ for $k\leq 4$, which improves these bounds. For
an assessment of the quality of these bounds, one should take into account
that, unless $P=NP$, the problem of finding the $k$-clustering that minimizes
the maximum diameter, for $k\geq 3$, does not admit an approximation better
than 2 in polytime (Megiddo, 1990).

For $k\geq 5$, the $k^{1.30}\textrm{OPT${}_{{\tt DM}}(k)$}$ upper bound does
not improve the factor of 8. However, our $k^{1.59}\textrm{OPT${}_{{\tt
AV}}(k)$}$ upper bound improves it for instances in which
$\textrm{OPT${}_{{\tt AV}}(k)$}\leq\frac{8}{k^{1.59}}\textrm{OPT${}_{{\tt
DM}}(k)$}$. Since $\frac{\textrm{OPT${}_{{\tt
DM}}(k)$}}{k}\leq\textrm{OPT${}_{{\tt AV}}(k)$}\leq\textrm{OPT${}_{{\tt
DM}}(k)$}$ , we can have improvements for $k\leq 34$.

An interesting aspect of our results is that they point in the opposite
direction of the common intuition that bottom-up methods for hierarchical
clustering do not work well for small $k$ and, hence, are less preferable than
bottom-up methods.

###  1.2 Related Work

Linkage methods are discussed in a number of research papers and books on data
mining and machine learning. Here, we discuss works that provide provable
guarantees for some of the most popular linkage methods.

Complete-link and Variants. Several upper and lower bounds are known on the
approximation factor for complete-linkage with respect to the maximum
diameter. When ${\cal X}=\mathbb{R}^{d}$, $d$ is constant and $dist$ is the
Euclidean metric, (Ackermann et al., 2010) proved that complete-linkage is an
$O(\log k\cdot\textrm{OPT${}_{{\tt DM}}(k)$})$ approximation. This was
improved by (Großwendt & Röglin, 2015) to $O(\textrm{OPT${}_{{\tt DM}}(k)$})$.
The dependence on $d$ is doubly exponential.

For general metric spaces, (Dasgupta & Long, 2005) showed that there are
instances for which the maximum diameter of the $k$-clustering built by
complete-linkage is $\Omega(\log k\cdot\textrm{OPT${}_{{\tt DM}}(k)$})$. In
(Arutyunova et al., 2021) this lower bound was improved to
$\Omega(k\cdot\textrm{OPT${}_{{\tt DM}}(k)$})$. Moreover, the same paper
showed that the maximum diameter of complete-linkage’s $k$-clustering is
$O(k^{2}\textrm{OPT${}_{{\tt DM}}(k)$})$. This result was recently improved by
the same authors to $O(k^{1.59}\textrm{OPT${}_{{\tt DM}}(k)$})$ (Arutyunova et
al., 2023). We note that the version of complete-linkage, analyzed in
(Arutyunova et al., 2021, 2023), merges at each iteration the two clusters $A$
and $B$ for which ${\tt diam}(A\cup B)$ is minimum. A consequence of
Proposition 2.1, presented here, is that this rule is equivalent to the
classical definition of complete-linkage presented at the beginning of Section
2.

(Arutyunova et al., 2023) also analysed minimax (Bien & Tibshirani, 2011), a
linkage method related to complete-linkage, that merges at each iteration the
two clusters $A$ and $B$ for which $A\cup B$ has the minimum ratio. They show
that the ${\tt max\mbox{-}diam}$ of the $k$-clustering built by minimax is
$\Theta(k\textrm{OPT${}_{{\tt DM}}(k)$})$. In Section 5, we show that the
${\tt max\mbox{-}diam}$ is also $O(k^{1,59}\textrm{OPT${}_{{\tt AV}}(k)$})$.
One disadvantage of this method is that while complete-linkage admits an
$O(n^{2})$ implementation (Defays, 1977), no sub-cubic time implementation for
minimax method is known (Bien & Tibshirani, 2011).

Single-link. Among linkage methods, single-linkage is likely the one with the
most extensive theoretical analysis (Kleinberg & Tardos, 2006; Dasgupta &
Long, 2005; Arutyunova et al., 2023; Laber & Murtinho, 2023).

The works of (Dasgupta & Long, 2005; Arutyunova et al., 2023) are those that
are more related to ours. The former shows that
$\Omega(k\cdot\textrm{OPT${}_{{\tt DM}}(k)$})$ is a lower bound on the maximum
diameter of Single-Link while the latter proves that this bound is tight. We
note that our $\Omega(k^{2}\cdot\textrm{OPT${}_{{\tt AV}}(k)$})$ lower bound
improves over that of (Dasgupta & Long, 2005) since $k\textrm{OPT${}_{{\tt
AV}}(k)$}\geq\textrm{OPT${}_{{\tt DM}}(k)$}$.

Average-link. (Dasgupta, 2016) introduced a global cost function defined over
the tree induced by a hierarchical clustering and proposed algorithms to
optimize it. (Cohen-Addad et al., 2019; Moseley & Wang, 2023) show that
average-linkage achieves constant approximation with respect to variants of
the cost functions proposed by (Dasgupta, 2016). (Charikar et al., 2019)
proved that these analyses are tight.

Ward. Another popular linkage method was proposed by (Ward, 1963). (Großwendt
et al., 2019) shows that Ward’s method gives a 2-approximation for $k$-means
when the optimal clusters are well-separated.

##  2 Preliminaries

Pseudo-code for complete-linkage is shown in Algorithm 2. The function ${\tt
dist}_{CL}(A,B)$ that measures the distance between clusters $A$ and $B$ is
given by

${\tt dist_{CL}}(A,B):=\max\\{dist(a,b)|(a,b)\in A\times B\\}.$

Algorithm 1 Hcomplete-linkage(${\cal X}$,dist,distL)

1: $\mathcal{C}^{0}\leftarrow$ clustering with $n$ unitary clusters, each one
containing a point of ${\cal X}$

2: For $i=1,\ldots,n-1$

3: $(A,B)\leftarrow$ clusters in $\mathcal{C}_{i-1}$ s.t. ${\tt
dist_{CL}}(A,B)$ is minimum

4: $\mathcal{C}^{i}\leftarrow\mathcal{C}^{i-1}\cup\\{A\cup B\\}-\\{A,B\\}$

Algorithm 2 Complete Link

The following property of complete-linkage, whose proof can be found in the
Appendix A, will be useful for our analysis. In particular, it implies that
the rule employed by complete-linkage is equivalent to the rule analysed in
(Arutyunova et al., 2023) that merges at each iteration the two clusters $A$
and $B$ for which ${\tt diam}(A\cup B)$ is minimum.

######  Proposition 2.1.

Let $A_{j}$ and $A^{\prime}_{j}$ be the clusters merged at the $j$th iteration
of complete-linkage. Then, for every $j\geq 1$,

${\tt diam}(A_{j}\cup A^{\prime}_{j})=\max\\{dist(x,y)|(x,y)\in A_{j}\times
A^{\prime}_{j}\\}$

and for every $j\geq 2$

${\tt diam}(A_{j}\cup A^{\prime}_{j})\geq{\tt diam}(A_{j-1}\cup
A^{\prime}_{j-1}).$

We conclude this section with some useful notation. The term _family_ is used
to denote a set of clusters. For a family $F$, we use $|F|$ and ${\tt
Pts}(F)$, respectively, to denote the number of clusters in $F$ and the set of
points that belong to some cluster in $F$, that is, ${\tt
Pts}(F)=\bigcup_{g\in F}g$ . Moreover, we use ${\tt diam}(F)$ to denote the
maximum distance between points that belong to ${\tt Pts}(F)$.

##  3 A first bound on the diameter of complete-link

In this section, we prove that the maximum diameter of the $k$-clustering
built by complete-linkage is at most $k^{1.59}\textrm{OPT${}_{{\tt AV}}(k)$}$.

Fix a target $k$-clustering $\mathcal{T}=(T_{1},\ldots,T_{k})$. Our proof
maintains a dynamic partition of the clusters produced by complete-linkage
into families, where the diameter of each such family $F$ can be bounded in
terms of the diameters of some of the $T_{i}$’s that it touches. We note that
our bounds will depend on the choice of $\mathcal{T}$ and we can take the best
possible $\mathcal{T}$ according to our objective. In this section, we take
$\mathcal{T}$ to be the $k$-clustering with minimum avg-diam.

In Algorithm 3, we define how the families evolve along the execution of
complete-linkage. At the beginning, each of the $|{\cal X}|$ points is a
cluster. We then define our first partition as $(F_{1},\ldots,F_{k})$, where
$F_{i}$ is a family that contains $|T_{i}|$ clusters, each one being a point
from $T_{i}$. Along the algorithm’s execution, the families are organized in a
directed forest $D$. Initially, the forest $D$ consists of $k$ isolated nodes,
where the $i$th node corresponds to family $F_{i}$.

When complete-linkage merges the clusters $g$ and $g^{\prime}$ belonging to
the families $F$ and $F^{\prime}$, respectively, a new family $F^{new}$ is
created and, in case (a) of Algorithm 3, a second new family
$F^{new^{\prime}}$ is also created. These new families contain all the
clusters in $F$ and $F^{\prime}$, except for $g$ and $g^{\prime}$ that are
replaced by the cluster $g\cup g^{\prime}$. Moreover, $F^{new}$ and
$F^{new^{\prime}}$ (when it is created) become parents of $F$ and $F^{\prime}$
in $D$. The precise definition of the new families and how the forest $D$ is
updated are given by cases $(a)$ and $(b)$ in Algorithm 3.

Algorithm 3 Partitioning the Clusters of complete-linkage

1: Create a clustering $\mathcal{C}^{0}$ with $n$ unitary clusters, each one
containing a point of ${\cal X}$

2: $\mathcal{T}=\\{T_{i}|1\leq i\leq k\\}\leftarrow$ $k$-clustering that
satisfies ${\tt avg\mbox{-}diam}(\mathcal{T})=\textrm{OPT${}_{{\tt AV}}(k)$}$

3: $F_{i}\leftarrow\\{\\{x\\}|x\in T_{i}\\},\,\forall i$

4: $D\leftarrow$ forest comprised of $k$ isolated nodes $F_{1},\ldots,F_{k}$.

5: For $t:=1,\ldots,n-k$

6: $(g,g^{\prime})\leftarrow$ next clusters to be merged by complete-linkage

7: $\mathcal{C}^{t}\leftarrow\mathcal{C}^{t-1}\cup\\{g\cup
g^{\prime}\\}-\\{g,g^{\prime}\\}$

8: Let $F$ and $F^{\prime}$ be the families associated with the roots of $D$
that respectively contain $g$ and $g^{\prime}$. Assume w.l.o.g.
$|F|\geq|F^{\prime}|$.

9: Proceed according to the following exclusive cases:

10: (case a) $|F^{\prime}|=1$ and $|F|>1$

11: $F^{new}\leftarrow F-\\{g\\}$; $F^{new^{\prime}}\leftarrow\\{g\cup
g^{\prime}\\}$

12: $F$.parent $\leftarrow$ $F^{new}$ ; $F^{\prime}$.parent $\leftarrow$
$F^{new^{\prime}}$

13: (case b) $|F^{\prime}|>1$ or $|F|=1$

14: $F^{new}\leftarrow(F\cup F^{\prime}\cup\\{g\cup
g^{\prime}\\})-g-g^{\prime}$

15: $F$.parent $\leftarrow$ $F^{new}$; $F^{\prime}$.parent $\leftarrow$
$F^{new}$

To prove our bound, we first show (Proposition 3.1) that at the beginning of
each iteration, there exists a family, among those associated with some root
of $D$, that contains at least two clusters. Then, we show an upper bound
(Proposition 3.2) on the diameter of every family, with at least two clusters,
created by Algorithm 3. Finally, in Theorem 3.3, this last result is used to
upper bound the diameter of every cluster created by complete-linkage, based
on a simple idea: if a cluster $g\cup g^{\prime}$ is created at iteration $t$
and $H$ is a family containing two clusters, say $h$ and $h^{\prime}$, at the
beginning of $t$, then complete-linkage rule guarantees that ${\tt diam}(g\cup
g^{\prime})\leq{\tt diam}(h\cup h^{\prime})\leq{\tt diam}(H)$.

For our analysis, we need some extra terminology. Let ${\tt leaves}(F)$ be the
set of leaves of the subtree of $D$ rooted at node/family $F$. We define
$\phi(F):=|{\tt leaves}(F)|$ and $\phi_{\Sigma}(F):=\sum_{H\in{\tt
leaves}(F)}{\tt diam}(H)$. Note that if a family $F^{new}$ is parent of both
families $F$ and $F^{\prime}$ in $D$ then
$\phi(F^{new})=\phi(F)+\phi(F^{\prime})$ and
$\phi_{\Sigma}(F^{new})=\phi_{\Sigma}(F)+\phi_{\Sigma}(F^{\prime})$ Moreover,
we say that a family $F$ is _regular_ if $|F|>1$ and it is a _singleton_ if
$|F|=1$.

######  Proposition 3.1.

At the beginning of each iteration of Algorithm 3, at least one of the roots
of $D$ corresponds to a regular family.

###### Proof.

Initially, the total number of roots of $D$ is $k$. Since the number of roots
either decreases or remains the same, the number of roots at the beginning of
each iteration is at most $k$. At the beginning of iteration $t$, for $t\leq
n-k$, the complete-linkage clustering $\mathcal{C}^{t}$ has more than $k$
clusters, each of them belonging to one family that is a root of $D$. Since
the number of roots is at most $k$, then there will be two different clusters
associated with the same root, so that this root corresponds to a regular
family. ∎

######  Proposition 3.2.

At the beginning of each iteration of Algorithm 3 the diameter of every
regular family $F$ satisfies ${\tt
diam}(F)\leq\phi_{\Sigma}(F)\cdot\phi(F)^{(\log_{2}3)-1}\leq
k^{\log_{2}3}\textrm{OPT${}_{{\tt AV}}(k)$}$.

###### Proof.

We have that $\phi(F)\leq k$, Moreover, the choice of the target clustering
$\mathcal{T}$ ensures that $\phi_{\Sigma}(F)\leq k\textrm{OPT${}_{{\tt
AV}}(k)$}$. Hence, the inequality $\phi_{\Sigma}(F)\phi(F)^{(\log_{2}3)-1}\leq
k^{\log_{2}3}\textrm{OPT${}_{{\tt AV}}(k)$}$ holds. Thus, we focus on the
first inequality.

The proof is by induction on the iteration of complete-linkage (and, in
parallel, of Algorithm 3). For every initial family $F_{i}$, $\phi(F_{i})=1$
and $\phi_{\Sigma}(F_{i})={\tt diam}(F_{i})$. Thus, for every $F_{i}$, ${\tt
diam}(F_{i})\leq\phi_{\Sigma}(F_{i})\phi(F_{i})^{(\log_{2}3)-1}$.

Let us assume by induction that the result at the beginning of iteration $t$.
We consider what happens in iteration $t$ according to the possible cases:

case (a). In this case, $F^{new^{\prime}}$ is a singleton so we do not need to
argue about it since the property is about regular families. Moreover, we have
that

$\displaystyle{\tt diam}(F^{new})={\tt diam}(F-\\{g\\})\leq{\tt diam}(F)\leq$
$\displaystyle\phi_{\Sigma}(F)\phi(F)^{\log_{2}3-1}=\phi_{\Sigma}(F^{new})\phi(F^{new})^{\log_{2}3-1},$

where the last inequality holds by induction and the last identity holds
because $\phi_{\Sigma}(F^{new})=\phi_{\Sigma}(F)$ and $\phi(F^{new})=\phi(F)$.

case (b) We split the proof into 3 subcases:

subcase 1. $|F|=1$ and $|F^{\prime}|=1$. In the case $F^{new}=\\{g\cup
g^{\prime}\\}$, so it is a singleton and, thus, there is nothing to argue
since the property is about regular families.

subcase 2. $|F^{\prime}|>1$ and $F$=$F^{\prime}$. In this case, we have

$\displaystyle{\tt diam}(F^{new})={\tt diam}(F)\leq$
$\displaystyle\phi_{\Sigma}(F)\phi(F)^{\log_{2}3-1}=\phi_{\Sigma}(F^{new})\phi(F^{new})^{\log_{2}3-1},$

where the inequality holds by induction and the last identity holds because
$\phi_{\Sigma}(F^{new})=\phi_{\Sigma}(F)$ and $\phi(F^{new})=\phi(F)$.

subcase 3. $|F^{\prime}|>1$ and $F\neq F^{\prime}$. This case is the most
interesting one. In this case, complete-linkage creates a new family $F^{new}$
by merging two clusters $g$ and $g^{\prime}$ from two distinct regular
families $F$ and $F^{\prime}$. Let $a$ and $b$ be two farthest points in ${\tt
Pts}(F^{new})$. If $a,b\in{\tt Pts}(F)$ or $a,b\in{\tt Pts}(F^{\prime})$ the
result holds for $F^{new}$ since

$\displaystyle{\tt diam}(F^{new})\leq\max\\{{\tt diam}(F),{\tt
diam}(F^{\prime})\\}\leq$
$\displaystyle\max\\{\phi_{\Sigma}(F)\cdot\phi(F)^{\log_{2}3-1},\phi_{\Sigma}(F^{\prime})\cdot\phi(F^{\prime})^{\log_{2}3-1}\\}\leq$
$\displaystyle\leq\phi_{\Sigma}(F^{new})\phi(F^{new})^{\log_{2}3-1}$

Let $a\in{\tt Pts}(F)$, $b\in{\tt Pts}(F^{\prime})$. We can assume w.l.o.g.
that

$\phi_{\Sigma}(F^{\prime})\cdot\phi(F^{\prime})^{(\log_{2}3)-1}\leq\phi_{\Sigma}(F)\cdot\phi(F)^{(\log_{2}3)-1}.$

Note that this assumption will not conflict with the assumption
$|F|\geq|F^{\prime}|$ that was made to facilitate the presentation of
Algorithm 3. Indeed, we do not use the assumption $|F|\geq|F^{\prime}|$ in
what follows.

Let $a^{\prime}\in g$ and $b^{\prime}\in g^{\prime}$ be points that satisfy
$dist(a^{\prime},b^{\prime})=\min\\{dist(x,y)|(x,y)\in g\times g^{\prime}\\}$.
Moreover, let $h$ and $h^{\prime}$ be any two clusters in $F$. We have that

$\displaystyle dist(a^{\prime},b^{\prime})\leq\max\\{dist(x,y)|(x,y)\in
g\times g^{\prime}\\}\leq$ (1) $\displaystyle\max\\{dist(x,y)|(x,y)\in h\times
h^{\prime}\\}\leq{\tt diam}(h\cup h^{\prime})\leq$ (2) $\displaystyle{\tt
diam}(F),$ (3)

where the second inequality follows from complete-linkage rule.

By symmetry we also have $dist(a^{\prime},b^{\prime})\leq{\tt
diam}(F^{\prime})$ and, hence

$dist(a^{\prime},b^{\prime})\leq\min\\{{\tt diam}(F),{\tt
diam}(F^{\prime})\\}$ (4)

Consider the sequence of points $a,a^{\prime},b^{\prime},b$. It follows from
the triangle inequality that

$\displaystyle{\tt diam}(F^{new})=dist(a,b)\leq$ (5) $\displaystyle\
dist(a,a^{\prime})+dist(a^{\prime},b^{\prime})+dist(b^{\prime},b)\leq$ (6)
$\displaystyle{\tt diam}(F)+{\tt diam}(F^{\prime})+{\tt diam}(F^{\prime})\leq$
(7)
$\displaystyle\phi_{\Sigma}(F)\phi(F)^{\log_{2}3-1}+2\phi_{\Sigma}(F^{\prime})\phi(F^{\prime})^{\log_{2}3-1}\leq$
(8)
$\displaystyle(\phi_{\Sigma}(F)+\phi_{\Sigma}(F^{\prime}))(\phi(F^{\prime})+\phi(F))^{\log_{2}3-1}=$
(9) $\displaystyle\phi_{\Sigma}(F^{new})\phi(F^{new})^{\log_{2}3-1},$ (10)

where inequality (6) follows from (4), inequality (7) follows from the
inductive hypothesis, inequality (8) follows from Proposition C.1 (with
$a=\phi_{\Sigma}(F)$, $b=\phi_{\Sigma}(F^{\prime})$, $x=\phi(F)$ and
$y=\phi(F^{\prime})$) and (9) holds because
$\phi(F^{new})=\phi(F)+\phi(F^{\prime})$ and
$\phi_{\Sigma}(F^{new})=\phi_{\Sigma}(F)+\phi_{\Sigma}(F^{\prime})$. ∎

Now, we state and prove the main result of this section.

######  Theorem 3.3.

For every $k$, the maximum diameter of the $k$-clustering built by complete-
linkage is at most $k^{\log_{2}3}\textrm{OPT${}_{{\tt AV}}(k)$}$.

###### Proof.

We prove by induction on the iteration of complete-linkage (and, in parallel,
of Algorithm 3) that the diameter of each cluster created by complete-linkage
is at most $k^{\log_{2}3}\textrm{OPT${}_{{\tt AV}}(k)$}$. At the beginning, we
have $n$ clusters, each of them corresponding to a point, so that for every
initial cluster $A$, ${\tt diam}(A)=0\leq k^{\log_{2}3}\textrm{OPT${}_{{\tt
AV}}(k)$}$. We assume by induction that at the beginning of iteration $t$
every cluster satisfies the desired property,

Let $g$ and $g^{\prime}$ be two clusters merged at iteration $t$. By
Proposition 3.1 there is a regular family $F$ at the beginning of the $t$-th
iteration. Let $h$ and $h^{\prime}$ be two clusters in $F$. Therefore,

$\displaystyle{\tt diam}(g\cup g^{\prime})=$ (11) $\displaystyle\max\\{{\tt
diam}(g),{\tt diam}(g^{\prime}),{\tt dist}_{CL}(g,g^{\prime})\\}\leq$ (12)
$\displaystyle\max\\{{\tt diam}(g),{\tt diam}(g^{\prime}),{\tt
dist}_{CL}(h,h^{\prime})\\}\leq$ (13) $\displaystyle\max\\{{\tt diam}(g),{\tt
diam}(g^{\prime}),{\tt diam}(h\cup h^{\prime})\\}\leq$ (14)
$\displaystyle\max\\{{\tt diam}(g),{\tt diam}(g^{\prime}),{\tt
diam}(F)\\}\leq$ (15) $\displaystyle k^{1.59}\textrm{OPT${}_{{\tt AV}}(k)$},$
(16)

where the first inequality holds due to the choice of complete-linkage and the
last one from the induction hypothesis and Proposition 3.2. ∎

single-linkage is a popular linkage method whose pseudo-code is obtained by
replacing ${\tt dist_{CL}}$ with ${\tt dist_{SL}}$ in Algorithm 2, where

${\tt dist_{SL}}(A,B):=\min\\{dist(a,b)|(x,y)\in A\times B\\},$

The rule employed by single-linkage, in contrast to that of complete-linkage,
is not greedy with respect to the minimization of the diameter. Thus, it is
expected that the latter presents better bounds than the former. However,
perhaps surprisingly, this is not the case when we consider approximation
regarding to OPTDM since the maximum diameter of the latter is
$\Omega(\textrm{OPT${}_{{\tt DM}}(k)$})$ while that of the former is
$\Theta(\textrm{OPT${}_{{\tt DM}}(k)$})$ (Arutyunova et al., 2023).

The use of OPTAV, instead of OPTDM, allows a separation between complete-
linkage and single-linkage in terms of worst-case approximation. In fact,
Theorem 3.3 shows that the maximum diameter of complete-linkage is at most
$k^{1.59}\textrm{OPT${}_{{\tt AV}}(k)$}$ while the next result shows that the
maximum diameter of single-linkage is $\Omega(k^{2}\textrm{OPT${}_{{\tt
AV}}(k)$})$.

######  Theorem 3.4.

There is an instance in which the $k$-clustering produced by single-linkage
includes a cluster of diameter $\Omega(k^{2}\textrm{OPT${}_{{\tt AV}}(k)$})$.

###### Proof.

We present a simple instance for which the $k$-clustering produced by single-
linkage has a cluster of diameter $\Omega(k^{2}\textrm{OPT${}_{{\tt
AV}}(k)$})$. Let $B$ be a large positive number and let us consider $k$ groups
$G_{1},\ldots,G_{k}$: $G_{1}$ consists of 2 points $a$ and $b$, with
$dist(a,b)=B$; the group $G_{i}$, for $1<i<k$ is a singleton, containing only
the point $x_{i}$; and the group $G_{k}$ consists of $k-1$ points
$y_{1},\ldots,y_{k-1}$, with $dist(y_{i},y_{j})=B+\epsilon$ for all $i$ and
$j$.

Moreover, we have that $dist(x_{i},a)=dist(x_{i},b)=(i-1)\times(B-\epsilon)$
for $i=2,\ldots,k-1$ and $dist(x_{i},x_{j})=(j-i)(B-\epsilon)$, for $1<i<j<k$.
Finally, the distance of any point in $G_{k}$ to a point outside $G_{k}$ is
$2B$.

Note that $(G_{1},\ldots,G_{k})$ is a $k$-clustering and the average diameter
of its clusters is $(2B+\epsilon)/k$. On the other hand, single-linkage builds
the $k-$clustering $(G_{1}\cup\cdots\cup
G_{k-1},\\{y_{1}\\},\ldots,\\{y_{k-1}\\})$ and the cluster
($G_{1}\cup\cdots\cup G_{k-1}$) has diameter $(k-1)(B-\epsilon)$. ∎

##  4 A Better Bound for Complete-Link

One of the key ideas of the approach presented in the previous section is to
use the diameter of a regular family to bound the diameter of any cluster that
is created. Indeed, if at the beginning of an iteration, there is a family $F$
with two clusters, then the diameter of the cluster created at this iteration
is at most ${\tt diam}(F)$. However, Algorithm 3 and its analysis do not take
full advantage of this idea. As an example, let us assume that at the
beginning of some iteration there are 3 regular families, say $F$,
$F^{\prime}$ and $F^{\prime\prime}$, with ${\tt diam}(F)\geq{\tt
diam}(F^{\prime})\geq{\tt diam}(F^{\prime\prime})$, all of them corresponding
to roots of $D$. If a cluster in $F$ is merged with one in $F^{\prime}$ (case
(b) of Algorithm 3) then a new family is created and its diameter is used as a
bound, which is not desirable since it is larger than that of
$F^{\prime\prime}$.

To obtain a better bound, instead of creating a new family whenever clusters
from different families, say $F$ and $F^{\prime}$, are merged, we create an
edge between $F$ and $F^{\prime}$ in a dynamic graph $G$ that keeps track of
the merges among different families. When a connected component of $G$ has at
most one family that can still be used as a bounding tool, we replace all
families in the component with a new family. The motivation for doing so is to
use a better bound as much as possible, which contrasts with the approach
taken by Algorithm 3.

This new approach is presented in Algorithm 4. The algorithm maintains a set
of excluded clusters ${\cal E}$; clusters in this set are never included in
the families that the algorithm creates (line 25). Moreover, it maintains both
a direct forest $D$ and a graph $G$. Each node of $G$ as well as each node of
$D$ is associated with a family; an edge is created in $G$ between
nodes/families $F$ and $F^{\prime}$ if complete-linkage merges two clusters
$g\notin{\cal E}$ and $g^{\prime}\notin{\cal E}$ that, respectively, contain
points from ${\tt Pts}(F)$ and ${\tt Pts}(F^{\prime})$. The graph and the
forest may be updated at each iteration of Algorithm 4.

Before giving extra details regarding Algorithm 4, we need to explain the
concept of a pure cluster. A family $F$ is created (lines 3 and 25) by
specifying the clusters that it contains. If a cluster $g$ is one of them, we
say that $g$ is pure w.r.t. $F$ or, alternatively, $F$ has the pure cluster
$g$. Moreover, if a cluster $g$ is obtained by merging two clusters that are
pure with respect to some family $F$ then $g$ is also pure w.r.t. $F$. If a
cluster is not pure w.r.t. any family, we say that it is non-pure. We use
${\tt pure}_{t}(F)$ to denote the number of pure clusters w.r.t. $F$ that
belong to $\mathcal{C}^{t}$. Note that if $pure_{t-1}(F)\geq 2$ then ${\tt
diam}(F)$ is an upper bound on the diameter of the cluster that is created at
iteration $t$, so that families with at least two pure clusters play a role
similar to that of regular families in the analysis of Algorithm 3.

In contrast to Algorithm 3, where each cluster belongs to one family, in
Algorithm 4 every cluster that does not belong to ${\cal E}$ is either pure
w.r.t. some family $F$ in $G$ (this would be equivalent of belonging to $F$)
or it is contained in $\bigcup_{H\in C}{\tt Pts}(H)$ for some connected
component $C$ in $G$. For our analysis, we note that ${\tt Pts}(F)$, ${\tt
diam}(F)$ and $|F|$ refer, respectively, to the set of points of $F$, the
diameter of $F$ and the number of clusters in $F$ at the moment that $F$ is
created.

The algorithm starts (lines 1-5) with the initialization of the set ${\cal
E}$, the forest $D$ and the graph $G$. Then, in the loop, two clusters are
merged following the complete-linkage rule. In terms of the graph, each merge
may lead to the addition of new edges and also to the union of two connected
components. In terms of the families, a merge can reduce by one unit the
number of pure clusters of one or two families. If this happens pure clusters
may be added to set ${\cal E}$ (lines 20 and 23) and this may also trigger one
of the cases (a), (b) or (c). If either (a) or (b) occurs a new family
$F_{C}$, associated with the component $C$ that satisfies one of these cases,
is created to replace all families in $C$ (line 25). If case (c) occurs the
component $C$ is removed from $G$.

The main loop was carefully designed to guarantee that (i) at the beginning of
each iteration there exists a family that has at least two pure clusters
associated with it and (ii) the diameter of family $F_{C}$ is slightly smaller
than twice the sum of the diameters of the families in the underlying
connected component $C$.

Algorithm 4 Tighter Bound for complete-linkage

1: $\mathcal{C}^{0}\leftarrow$ clustering with $n$ unitary clusters, each one
containing a point of ${\cal X}$

2: $(T^{*}_{1},\ldots,T^{*}_{k})\leftarrow$ a $k$-clustering with maximum
diameter equal to OPT${}_{{\tt DM}}(k)$

3: For each $i$, with $|T^{*}_{i}|>1$, $F_{i}\leftarrow\\{\\{x\\}|x\in
T^{*}_{i}\\}$

4: Create a forest $D$ with no edges and vertex set $\\{F_{i}|T^{*}_{i}\mbox{
has at least two points}\\}$

5: Create a graph $G$ with no edges and vertex set $\\{F_{i}|T^{*}_{i}\mbox{
has at least two points}\\}$

6: ${\cal E}\leftarrow$ set of clusters $T^{*}_{i}$ with exactly one point

7: For $t:=1\ldots n-k$

8: $(g,g^{\prime})\leftarrow$ next clusters to be merged by Complete-Link

9: $\mathcal{C}^{t}\leftarrow\mathcal{C}^{t-1}\cup\\{g\cup
g^{\prime}\\}-\\{g,g^{\prime}\\}$

10: If $g$ or $g^{\prime}$ is a cluster in ${\cal E}$

11: Add $g\cup g^{\prime}$ to ${\cal E}$ and remove from ${\cal E}$ the
clusters in $\\{g,g^{\prime}\\}$ that belong to ${\cal E}$

12: Else

13: Create edges between all families $F$ and $F^{\prime}$ such that ${\tt
Pts}(F)$ has a point in $g$ and ${\tt Pts}(F^{\prime})$ has a point in
$g^{\prime}$

14: Consider the following exclusive cases:

15: (a) $\exists$ connected component $C$ in $G$, with $|C|>1$, that has
exactly one family $F$ such that ${\tt pure}_{t}(F)>1$

16: (b) $\exists$ connected component $C$ in $G$, with $|C|>1$, such that
every family $F$ in $C$ satisfies ${\tt pure}_{t}(F)\leq 1$

17: (c) $\exists$ connected component $C$ in $G$, with $|C|=1$, and its only
family $F$ satisfies ${\tt pure}_{t}(F)\leq 1$

18: If $(b)$ does not occur

19: For each family $H$ in $G$ that satisifies ${\tt pure}_{t-1}(H)>1$ and
${\tt pure}_{t}(H)=1$

20: Add the pure cluster in $H$ to ${\cal E}$

21: If (b) occurs

22: $H\leftarrow$ some family in $C$ such that ${\tt pure}_{t-1}(H)>1\mbox{
and }{\tt pure}_{t}(H)=1$

23: Add the pure cluster in $H$ to ${\cal E}$

24: If either $(a)$ or $(b)$ occurs

25: Create family $F_{C}:=\\{h|h\in\mathcal{C}^{t}\mbox{ and
}h\subseteq\bigcup_{H\in C}{\tt Pts}(H)\\}\setminus{\cal E}$

26: Set $F_{C}$ as the parent, in the forest $D$, of every family of $C$

27: Add to $G$ a node corresponding to $F_{C}$

28: Remove all families in the connected component $C$ from $G$

29: If $(c)$ occurs

30: Remove all families in the connected component $C$ from $G$

The roadmap to establish our improved bound (Theorem 4.5) consists of first
showing that (i) holds (Lemma 4.1) and, then, showing an upper bound on the
diameters of the families $F_{C}$ that are created in line 25. This upper
bound will be used to bound the diameter of every cluster that is created by
complete-linkage. Note that our strategy is similar to that employed to prove
Theorem 3.3. However, the proofs here are significantly more involved.

We start with Lemma 4.1. We present an overview of the proof and we refer to
Appendix B for the full proof.

######  Lemma 4.1.

For $t\leq n-k$, at the beginning of iteration $t$ of Algorithm 4, each
connected component $C$ of $G$ satisfies one of the following properties: (i)
$|C|=1$ and the only family of $C$ has at least two pure clusters or (ii)
$|C|>1$ and there exist two families in $C$ such that each of them has at
least two pure clusters.

###### Proof Sketch.

We first argue that if all components of $G$ satisfy the desired properties at
the beginning of iteration $t$ then all components of $G$ also satisfy them at
the beginning of iteration $t+1$. Next, we argue that $G$ does not have all
its nodes removed at some iteration.

At the beginning of Algorithm 4, all the components in $G$ satisfy property
(i) because, by line 5, all the families $F_{i}$ in $G$ have at least two
clusters and all their clusters are pure.

When two clusters are merged at some iteration $t$, then at most two distinct
families have their number of pure clusters decreased by one unit (Proposition
B.1). As a result, one connected component, say $C$, where these families lie
in the updated graph may not respect the conditions of the lemma anymore.
However, in this case, we can show that either (a), (b) or (c) occurs. In the
case (c), the component $C$ is removed from $G$, so we do not have a problem
with $C$ at the next iteration. If either (a) or (b) occurs, $C$ is replaced
with a new component that only has the family $F_{C}$. Proposition B.2 shows
that there are two pure clusters w.r.t. $F_{C}$, so this new component
satisfies the condition (i).

Now, assume that $G$ has all its nodes removed at some iteration $t^{\prime}$.
It is possible to conclude that at the beginning of $t^{\prime}$, $G$ has just
one component, this component has just one family and this family has exactly
2 pure clusters. This together with the fact that at most $k$ clusters are
added to ${\cal E}$ (Proposition B.4) allows the conclusion that there are at
most $k+1$ clusters at the beginning of $t^{\prime}$. But this is not a
problem since $t^{\prime}\geq n-k$ in this case. ∎

Now, we bound the diameter of the families $F_{C}$ at the moment they are
created by Algorithm 4. To this end, we define a spanning tree $T_{C}$ for $C$
and use its paths to bound the diameter of $F_{C}$. Consider the sequence of
merges $m_{1},\ldots,m_{|C|-1}$, between clusters, that builds the connected
component $C$, that is, right after each merge at least two families in $C$
that were not connected become connected. Moreover, let $g_{i}$ be cluster
produced by merging $m_{i}$. The nodes of $T_{C}$ are the families in $C$ and
the edges of $T_{C}$ are defined as follows: for each merge $m_{i}$ we create
an edge $e_{i}$ between two arbitrarily chosen families, say $F^{1}$ and
$F^{2}$, among those that were not connected before merge $m_{i}$ and also
have points in $g_{i}$, that is, ${\tt Pts}(F^{1})\cap g_{i}\neq\emptyset$ and
${\tt Pts}(F^{2})\cap g_{i}\neq\emptyset$. The weight of $e_{i}$ is given by
the diameter of $g_{i}$.

For the following results, let DMi be the $i$th smallest diameter among the
families that belong to $C$.

######  Proposition 4.2.

The weight of the cheapest edge of $T_{C}$ is at most DM1 and, for $i>1$, the
weight of its $i$th cheapest edge is at most DMi-1.

###### Proof.

Let $F$ be a family that has at least two pure clusters right before the merge
$m_{i}$ and let $h$ and $h^{\prime}$ be two pure clusters w.r.t. $F$. We first
note that

${\tt diam}(g_{i})\leq\max\\{dist(x,y)|(x,y)\in h\times h^{\prime}\\}\leq{\tt
diam}(h\cup h^{\prime})\leq{\tt diam}(F),$

where the first inequality holds due to the choice of Complete-Link and
Proposition 2.1. Moreover,

${\tt diam}(g_{i})\leq{\tt diam}(F^{\prime})$

for any family in $C$ that does not exist before the merge. In fact, by
condition (i) of Lemma 4.1 $F^{\prime}$ is created with at least two clusters,
say $h$ and $h^{\prime}$, and ${\tt diam}(g_{i})\leq{\tt diam}(h\cup
h^{\prime})\leq{\tt diam}(F^{\prime})$, where the first inequality follows
from Proposition 2.1. Hence, we can conclude that ${\tt diam}(g_{1})\leq{\tt
DM}_{1}$ because before the first merging each family in $C$ that already
exists is an isolated node in $G$ and has at least two pure clusters
(condition (i) of Lemma 4.1).

Now, we consider the case $i>1$. Let $a$ be the number of families in $C$ that
have at least two pure clusters right before the merge $m_{i}$ and let $b$ be
the number of families in $C$ that have not been created yet. It is enough to
show that $a+b\geq|C|-i+2$ (claim below). In fact, in this case $|C|-i+2$
families in $C$ have diameter not smaller than ${\tt diam}(g_{i})$ so that
${\tt diam}(g_{i})\leq{\tt DM}_{i-1}$

Claim. $a+b\geq|C|-i+2$

Proof. Right before $m_{i}$, the families in $C$ are distributed in
$(|C|-b)-i+1$ connected components in the graph $G$. If one of these
components has just one family, it follows from condition (i) of Lemma 4.1
that this family must have at least two pure clusters. If one of these
components has at least two families, then it follows from condition (ii) of
Lemma 4.1 that there are two families in this component, each of them with at
least two pure clusters.

Since $i>1$, at least one component has at least two families. Thus, there are
at least $(|C|-b)-i+2$ families with at least two pure clusters right before
$m_{i}$. We conclude that $a\geq(|C|-b)-i+2$ and, hence, $a+b\geq|C|-i+2$

End of Proof. ∎

The next proposition gives an upper bound on the diameter of $F_{C}$ as a
function of the diameters of the families in the component $C$ associated with
$F_{C}$. In high-level, its proof considers the path $P$ in $T_{C}$ between
the families where the two farthest points in ${\tt Pts}(F_{C})$ lie and then
use the triangle inequality to show that the distance between these points is
upper bounded by the sum of the weights of the edges in $P$ plus the sum of
the diameters of the nodes/families in $P$. This sum, however, is upper
bounded by the sum of the diameters of all the families in $C$ plus the sum of
the weights of the edges in $T_{C}$, so that

${\tt diam}(F_{C})\leq\sum_{i=1}^{|C|}{\tt DM}_{i}+\left({\tt
DM}_{1}+\sum_{i=1}^{|C|-2}{\tt DM}_{i}\right).$

The proposition, in fact, shaves ${\tt DM}_{1}$ from the above upper bound via
a more careful analysis.

######  Proposition 4.3.

Let $F_{C}$ be a family associated with the connected component $C$ of $G$ in
line 25 of Algorithm 4. Then, when $F_{C}$ is created, we have

${\tt diam}(F_{C})\leq\sum_{i=1}^{|C|}{\tt DM}_{i}+\sum_{i=1}^{|C|-2}{\tt
DM}_{i}$

###### Proof.

For a given point $x$, we use $F_{x}$ to denote the family in connected
component $C$ where $x$ lies right before the families in $C$ are replaced
with $F_{C}$. Let $a$ and $b$ be the two farthest points of $F_{C}$. We split
the proof into two cases:

Case i) The path from the family $F_{a}$ to $F_{b}$ in $T_{C}$ has less than
$|C|-1$ edges.

Let $u_{1},\ldots,u_{t}$, with $u_{1}=F_{a}$ and $u_{t}=F_{b}$, be such a
path. Note that $t<|C|$. Recall that in the construction of $T_{C}$, an edge
between families $u_{i}$ and $u_{u+1}$ is associated with some cluster $g$.
Let $p^{\prime}_{i}$ and $p_{i+1}$ be, respectively, arbitrarily chosen points
in ${\tt Pts}(u_{i})$ and ${\tt Pts}(u_{i+1})$ that belong to $g$. Now,
consider the sequence of points
$(a=p_{1},p^{\prime}_{1},p_{2},p^{\prime}_{2},\ldots,p_{t},p^{\prime}_{t}=b)$.
We have that

$\displaystyle{\tt diam}(F_{C})=dist(a,b)\leq$
$\displaystyle\sum_{i=1}^{t}dist(p_{i},p^{\prime}_{i})+\sum_{i=1}^{t-1}dist(p^{\prime}_{i},p_{i+1})\leq$
$\displaystyle\sum_{i=2}^{|C|}{\tt DM}_{i}+\sum_{i=1}^{|C|-2}{\tt DM}_{i},$

where the first inequality holds due to the triangle inequality and for the
second one we use the fact that $\sum_{i=1}^{t}dist(p_{i},p^{\prime}_{i})$ can
be upper bounded by the $|C|-1$ largest diameters of the families in $C$ and
Proposition 4.2 assures that $\sum_{i=1}^{t-1}dist(p^{\prime}_{i},p_{i+1})$
can be upper bounded by the sum of the weights of the $|C|-2$ most expensive
edges of $T_{C}$.

Case ii) The path from $F_{a}$ to $F_{b}$ in $T_{C}$ has $|C|-1$ edges.

Since $|C|>1$ we have that $F_{a}\neq F_{b}$. It follows from Proposition B.3
that there is $y\in\\{a,b\\}$ such that a pure cluster w.r.t. family $F_{y}$
is added to ${\cal E}$, before the creation of $F_{C}$, by either line 20 or
line 23.

We assume w.l.o.g. that $y=a$. Let $g$ be the pure cluster w.r.t. $F_{a}$ that
is added to ${\cal E}$. We assume that $F_{C}$ is created at iteration $t$ and
the addition of $g$ to ${\cal E}$ happened at iteration $t^{\prime}$, so that
$t^{\prime}\leq t$. We cannot have $a\in g$ because points that belong to
clusters in ${\cal E}$ are not in ${\tt Pts}(F_{C})$. Moreover, $a$ cannot be
in a pure cluster w.r.t. $F_{a}$ after the $t^{\prime}$-th merge, otherwise we
would have ${\tt pure}_{t^{\prime}}(F_{a})\geq 2$ and $g$ would not have been
added to ${\cal E}$. Thus, right after the $t^{\prime}$-th merge, $a$ belongs
to a cluster that contains a point, say $x$, from a family $F_{x}$ different
from $F_{a}$.

We must have

$dist(a,x)\leq{\tt diam}(F_{a})$ (17)

since the cluster that contains $a$ and $x$ was created when $F_{a}$ still had
at least two pure clusters.

Now consider the path ($F_{x}=v_{1},\ldots,v_{t}=F_{b}$) from $F_{x}$ to
$F_{b}$ in $T_{C}$. This path does not include $F_{a}$, otherwise the path
from $F_{a}$ to $F_{b}$ would have at most $|C|-2$ edges, which is not
possible since we are in case (ii). If the edge in $T_{C}$ that connects
families $v_{i}$ to $v_{u+1}$ corresponds to cluster $g$ then choose
$p^{\prime}_{i}$ and $p_{i+1}$ as points in $v_{i}$ and $v_{i+1}$,
respectively, that belong to $g$. Now, consider a sequence of points
$(a,p_{1},p^{\prime}_{1},p_{2},p^{\prime}_{2},\ldots,p_{t},p^{\prime}_{t})$,
where $p_{1}=x$ and $p^{\prime}_{t}=b$. From the triangle inequality,

$dist(a,b)\leq
dist(a,x)+\sum_{i=1}^{t}dist(p_{i},p^{\prime}_{i})+\sum_{i=1}^{t-1}dist(p^{\prime}_{i},p_{i+1}).$

Moreover, we have

$\sum_{i=1}^{t}dist(p_{i},p^{\prime}_{i})\leq\sum_{i=1}^{|C|}{\tt DM}_{i}-{\tt
diam}(F_{a})$

and due to Proposition 4.2

$\sum_{i=1}^{t-1}dist(p^{\prime}_{i},p_{i+1})\leq\sum_{i=2}^{|C|-1}{\tt
DM}_{i-1},$

Hence,

$\displaystyle dist(a,b)\leq$ $\displaystyle dist(a,x)-{\tt
diam}(F_{a})+\sum_{i=1}^{|C|}{\tt DM}_{i}+\sum_{i=2}^{|C|-1}{\tt
DM}_{i-1}\leq$ $\displaystyle\sum_{i=1}^{|C|}{\tt
DM}_{i}+\sum_{i=2}^{|C|-1}{\tt DM}_{i-1}=\sum_{i=1}^{|C|}{\tt
DM}_{i}+\sum_{i=1}^{|C|-2}{\tt DM}_{i},$

where the last inequality follows from (17). ∎

For the next lemma recall that $\phi(F)=|{\tt leaves}(F)|$, where ${\tt
leaves}(F)$ is the set of leaves in the subtree of $D$ rooted at node/family
$F$.

Let $\alpha=\max\\{\frac{\log(2i-2)}{\log i}|i\mbox{ is a natural number
larger than 1}\\}$. Proposition C.2 shows that $\alpha=\frac{\log 6}{\log
4}<1.30$. Moreover, we define $\alpha_{k}=\log_{k}(2k-2)$, if $k\leq 4$, and
$\alpha_{k}=\alpha$ for $k>4$.

######  Lemma 4.4.

Every family $F$ created by Algorithm 4 satisfies ${\tt
diam}(F)\leq\textrm{OPT${}_{{\tt DM}}(k)$}\phi(F)^{\alpha_{k}}$.

###### Proof.

The initial families $F_{i}$ satisfies the property because ${\tt
diam}(F_{i})={\tt diam}(T^{*}_{i})\leq\textrm{OPT${}_{{\tt
DM}}(k)$}\leq\textrm{OPT${}_{{\tt DM}}(k)$}\phi(F_{i})^{\alpha_{k}}$ since
$\phi(F_{i})=1$.

Let us assume that the result holds at the beginning of iteration $t$. If no
family is created at iteration $t$ the result holds at the beginning of
iteration $t+1$. Otherwise, a family $F_{C}$, associated with a connected
component $C$, is created. Let $\\{F_{C}^{i}|i=1,\ldots,|C|\\}$ be the
nodes/families in $C$ right before the creation of $F_{C}$. Moreover, assume
that $\phi(F_{C}^{i})\leq\phi(F_{C}^{i+1})$. We have that

$\displaystyle{\tt diam}(F_{c})\leq$ (18) $\displaystyle\sum_{i=1}^{|C|}{\tt
DM}_{i}+\sum_{i=1}^{|C|-2}{\tt DM}_{i}\leq$ (19)
$\displaystyle\sum_{i=1}^{|C|}{\tt diam}(F_{C}^{i})+\sum_{i=1}^{|C|-2}{\tt
diam}(F_{C}^{i})\leq$ (20) $\displaystyle\textrm{OPT${}_{{\tt
DM}}(k)$}\cdot\left(\sum_{i=1}^{|C|}\phi(F_{C}^{i})^{\alpha_{k}}+\sum_{i=1}^{|C|-2}\phi(F_{C}^{i})^{\alpha_{k}}\right)\leq$
(21) $\displaystyle\textrm{OPT${}_{{\tt
DM}}(k)$}\left(\sum_{i=1}^{|C|}\phi(F_{C}^{i})\right)^{\alpha_{k}}=\textrm{OPT${}_{{\tt
DM}}(k)$}\phi(F_{C})^{\alpha_{k}},$ (22)

where (18) follows from Proposition 4.3; (19) holds because ${\tt
DM}_{1},\ldots,{\tt DM}_{|C|-2}$ are the $|C|-2$ smallest diameters among the
diameters of the families in $C$; (20) follows from the inductive hypothesis
and (21) follows from Proposition C.3, using $a_{i}=\phi(F_{C}^{i})$,
$\ell=|C|$ and $p=\alpha_{k}.$ ∎

We can state the main result of this section, its proof is very similar to
that of Theorem 3.3.

######  Theorem 4.5.

The maximum diameter among the clusters of the $k$-clustering produced by
complete-linkage is at most $(2k-2)\textrm{OPT${}_{{\tt DM}}(k)$}$, if $k\leq
4$, and at most $k^{1.30}\textrm{OPT${}_{{\tt DM}}(k)$}$, if $k>4$.

###### Proof.

Due to the definition of $\alpha_{k}$, it is enough to show that the diameter
of every cluster created by complete-linkage is at most $\textrm{OPT${}_{{\tt
DM}}(k)$}\cdot k^{\alpha_{k}}$.

We prove it by induction on the number of iterations of the Algorithm 4. At
the beginning, all $n$ clusters have a diameter of 0, so the result holds.

We assume by induction that the result holds at the beginning of iteration
$t$. At the beginning of this iteration, by Lemma 4.1 there is a family, say
$F$, with at least 2 pure clusters. Let $h$ and $h^{\prime}$ be these
clusters. Moreover, let $g$ and $g^{\prime}$ be the clusters merged at
iteration $t$. We have that

$\displaystyle{\tt diam}(g\cup g^{\prime})=$ $\displaystyle\max\\{{\tt
diam}(g),{\tt diam}(g^{\prime}),{\tt dist}_{CL}(g,g^{\prime})\\}\leq$
$\displaystyle\max\\{{\tt diam}(g),{\tt diam}(g^{\prime}),{\tt
dist}_{CL}(h,h^{\prime})\\}\leq$ $\displaystyle\max\\{{\tt diam}(g),{\tt
diam}(g^{\prime}),{\tt diam}(h\cup h^{\prime})\\}\leq$
$\displaystyle\max\\{{\tt diam}(g),{\tt diam}(g^{\prime}),{\tt
diam}(F)\\}\leq$ $\displaystyle\textrm{OPT${}_{{\tt DM}}(k)$}k^{\alpha_{k}}$

where the first inequality is due to the choice of complete-linkage and the
last inequality holds due to Lemma 4.4, the inductive hypothesis and the fact
that $\phi(k)\leq k$. ∎

We note that $k=2$, $k=3$ and $k=4$, we get approximation factors of $2$, $4$
and $6$, respectively. For $k>4$ the approximation factor is
$k^{\log_{4}6}\leq k^{1.30}.$

##  5 Other linkage methods

In this last section, we show that Theorem 3.3 generalizes to a class of
linkage methods that includes minimax and the quite popular average-linkage.

Let $f$ be a distance function that maps a pair of clusters into a non-
negative real number and let Linkf be a linkage method that follows the
pseudo-code of Algorithm 2, with the exception that it uses the function $f$,
rather than distCL, to measure the distance between two clusters. Moreover,
for a cluster $A$, let ${\tt cost}(A)$ be a cohesion criterion (e.g.
diameter). We say that $f$ and ${\tt cost}$ align if they satisfy the
following conditions for every pair of disjoint clusters $A$ and $B$:

(i) $\min\\{{\tt dist}(a,b)|(a,b)\in A\times B\\}\leq f(A,B)\leq{\tt
diam}(A\cup B)$;

(ii) ${\tt cost}(A)=0$ if $|A|=1$;

(iii) ${\tt cost}(A\cup B)\leq\min\\{{\tt cost}(A),{\tt cost}(B),f(A,B)\\}$

Theorem 5.2 presented below is a generalization of Theorem 3.3. In fact, from
the former, we can recover the latter by setting ${\tt cost}={\tt diam}$ and
$f={\tt dist}_{CL}$. The proof of Theorem 5.2 is essentially the same as that
of Theorem 3.3, but for a few differences that we explain in what follows.

The proof of Theorem 5.2 is based on the analysis of the families generated by
the variation of Algorithm 3 that uses a distance function $f$ that satisfies
(i), rather than ${\tt dist}_{CL}$, to decide which clusters are merged at
each iteration. We use Algof to denote this modified version of Algorithm 3.

Proposition 3.1 does not depend on the distance function employed to decide
which clusters shall be merged at each iteration, so it is still valid for
Algof.

The following proposition generalizes Proposition 3.2 for linkage methods
whose underlying distances satisfy condition (i).

######  Proposition 5.1.

If $f$ satisfies condition (i), then at the beginning of each iteration of
Algof the diameter of every regular family $F$ satisfies

${\tt diam}(F)\leq\phi_{\Sigma}(F)\cdot\phi(F)^{(\log_{2}3)-1}\leq
k^{\log_{2}3}\textrm{OPT${}_{{\tt AV}}(k)$}.$

###### Proof.

In Proposition 3.2, the complete-linkage’s rule is just used to prove
inequalities (1)-(3). However, these inequalities are valid if the function
$f$ satisfies condition (i). In fact, we have

$dist(a^{\prime},b^{\prime})\leq f(g,g)\leq f(h,h^{\prime})\leq{\tt
diam}(h\cup h^{\prime})\leq\\\ {\tt diam}(F),$

where the first and the third inequality hold due to condition (i) while the
second holds due to the choice of Linkf. ∎

######  Theorem 5.2.

If $f$ and ${\tt cost}$ align, then the $k$-clustering $\mathcal{C}$ built by
Linkf satisfies

$\max\\{{\tt cost}(C)|C\in\mathcal{C}\\}\leq k^{1.59}\textrm{OPT${}_{{\tt
AV}}(k)$}$

###### Proof.

We prove by induction on the number of iterations of Linkf (in parallel on
Algof) that each cluster $A$ created by Linkf satisfies ${\tt cost}(A)\leq
k^{\log_{2}3}\textrm{OPT${}_{{\tt AV}}(k)$}$. At the beginning, this holds
because every cluster $A$ is a point, so that ${\tt cost}(A)=0$ due to
condition (ii). We assume by induction that the desired property holds at the
beginning of iteration $t$.

Let $g$ and $g^{\prime}$ be two clusters merged at iteration $t$. By
Proposition 3.1 there is a regular family $F$ at the beginning of the $t$-th
iteration. Let $h$ and $h^{\prime}$ be two clusters in $F$. Therefore,

$\displaystyle{\tt cost}(g\cup g^{\prime})\leq$ (23) $\displaystyle\max\\{{\tt
cost}(g),{\tt cost}(g^{\prime}),f(g,g^{\prime})\\}\leq$ (24)
$\displaystyle\max\\{{\tt cost}(g),{\tt
cost}(g^{\prime}),f(h,h^{\prime})\\}\leq$ (25) $\displaystyle\max\\{{\tt
cost}(g),{\tt cost}(g^{\prime}),{\tt diam}(h\cup h^{\prime})\\}\leq$ (26)
$\displaystyle\max\\{{\tt cost}(g),{\tt cost}(g^{\prime}),{\tt
diam}(F)\\}\leq$ (27) $\displaystyle k^{1.59}\textrm{OPT${}_{{\tt AV}}(k)$}$
(28)

where the first inequality holds due to condition (iii), the second due to the
choice of Linkf, the third due to condition (i) and the last one follows from
induction and Proposition 5.1. ∎

Now, we specialize Theorem 5.2 for average-linkage and minimax. average-
linkage employs the distance function

${\tt dist}_{AL}(A,B)=\frac{1}{|A|\cdot|B|}\sum_{a\in A}\sum_{b\in
B}dist(a,b)$

to measure the distance between clusters $A$ and $B$. Clearly, ${\tt
dist}_{AL}$ satisfies condition (i). For a cluster $A$, we define ${\tt
avg}(A)$ as $0$ if $|A|=1$ and as the average pairwise distance of the points
in $A$ if $|A|>1$, that is,

${\tt avg}(A):=\frac{2}{|A|(|A|-1)}\sum_{x,y\in A}dist(x,y).$

Since ${\tt avg}(A\cup B)$ is a convex combination of ${\tt avg}(A)$, ${\tt
avg}(B)$ and ${\tt dist}_{AL}(A,B)$, condition (iii) is also satisfied and,
therefore, ${\tt dist}_{AL}$ and ${\tt avg}$ align. We have the following
result.

######  Theorem 5.3.

For every $k$, the $k$-clustering $\mathcal{C}$ built by average-linkage
satisfies

$\max\\{{\tt avg}(C)|C\in\mathcal{C}\\}\leq k^{1.59}\textrm{OPT${}_{{\tt
AV}}(k)$}$

Now we consider the minimax linkage method. This method employs the function

${\tt dist}_{MM}(A,B):=\min_{x\in A\cup B}\max_{y\in A\cup B}dist(x,y).$

to measure the distance between clusters.

We have that ${\tt dist}_{MM}$ satisfies (i). Consider the cohesion criterion
${\tt radius}(A)$ that has value 0 if $|A|=1$ and when $|A|>1$,

${\tt radius}(A):=\min_{x\in A}\max_{y\in A}dist(x,y).$

Since ${\tt radius}(A\cup B)={\tt dist}_{MM}(A,B)$ the condition (iii) is also
satisfied and, hence, ${\tt dist}_{MM}$ and ${\tt radius}$ align. We have that

######  Theorem 5.4.

For every $k$, the $k$-clustering $\mathcal{C}$ built by minimax satisfies

$\max\\{{\tt radius}(C)|C\in\mathcal{C}\\}\leq k^{1.59}\textrm{OPT${}_{{\tt
AV}}(k)$}.$

## References

  * Ackerman & Ben-David (2016) Ackerman, M. and Ben-David, S.  A characterization of linkage-based hierarchical clustering.  _J. Mach. Learn. Res._ , 17:232:1–232:17, 2016.  URL http://jmlr.org/papers/v17/11-198.html.
  * Ackermann et al. (2010) Ackermann, M. R., Blömer, J., Kuntze, D., and Sohler, C.  Analysis of agglomerative clustering.  _CoRR_ , abs/1012.3697, 2010.  URL http://arxiv.org/abs/1012.3697.
  * Arutyunova & Röglin (2022) Arutyunova, A. and Röglin, H.  The price of hierarchical clustering.  In Chechik, S., Navarro, G., Rotenberg, E., and Herman, G. (eds.), _30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany_ , volume 244 of _LIPIcs_ , pp. 10:1–10:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi: 10.4230/LIPICS.ESA.2022.10.  URL https://doi.org/10.4230/LIPIcs.ESA.2022.10.
  * Arutyunova et al. (2021) Arutyunova, A., Großwendt, A., Röglin, H., Schmidt, M., and Wargalla, J.  Upper and Lower Bounds for Complete Linkage in General Metric Spaces.  In Wootters, M. and Sanità, L. (eds.), _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)_ , volume 207 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pp. 18:1–18:22, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-207-5.  doi: 10.4230/LIPIcs.APPROX/RANDOM.2021.18.  URL https://drops.dagstuhl.de/opus/volltexte/2021/14711.
  * Arutyunova et al. (2023) Arutyunova, A., Großwendt, A., Röglin, H., Schmidt, M., and Wargalla, J.  Upper and lower bounds for complete linkage in general metric spaces.  _Machine Learning_ , pp. 1–30, 2023.
  * Bien & Tibshirani (2011) Bien, J. and Tibshirani, R.  Hierarchical clustering with prototypes via minimax linkage”.  _Journal of the American Statistical Association_ , 106:1075–1084, 2011.
  * Charikar et al. (2004) Charikar, M., Chekuri, C., Feder, T., and Motwani, R.  Incremental clustering and dynamic information retrieval.  _SIAM J. Comput._ , 33(6):1417–1440, 2004.  doi: 10.1137/S0097539702418498.  URL https://doi.org/10.1137/S0097539702418498.
  * Charikar et al. (2019) Charikar, M., Chatziafratis, V., and Niazadeh, R.  Hierarchical clustering better than average-linkage.  In Chan, T. M. (ed.), _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019_ , pp. 2291–2304. SIAM, 2019.  doi: 10.1137/1.9781611975482.139.  URL https://doi.org/10.1137/1.9781611975482.139.
  * Cohen-Addad et al. (2019) Cohen-Addad, V., Kanade, V., Mallmann-Trenn, F., and Mathieu, C.  Hierarchical clustering: Objective functions and algorithms.  _J. ACM_ , 66(4):26:1–26:42, 2019.  doi: 10.1145/3321386.  URL https://doi.org/10.1145/3321386.
  * Dasgupta (2016) Dasgupta, S.  A cost function for similarity-based hierarchical clustering.  In Wichs, D. and Mansour, Y. (eds.), _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , pp. 118–127. ACM, 2016.  doi: 10.1145/2897518.2897527.  URL https://doi.org/10.1145/2897518.2897527.
  * Dasgupta & Long (2005) Dasgupta, S. and Long, P. M.  Performance guarantees for hierarchical clustering.  _Journal of Computer and System Sciences_ , 70(4):555–569, 2005.  ISSN 0022-0000.  doi: https://doi.org/10.1016/j.jcss.2004.10.006.  URL https://www.sciencedirect.com/science/article/pii/S0022000004001321.  Special Issue on COLT 2002.
  * Defays (1977) Defays, D.  An efficient algorithm for a complete link method.  _Comput. J._ , 20(4):364–366, 1977.  doi: 10.1093/COMJNL/20.4.364.  URL https://doi.org/10.1093/comjnl/20.4.364.
  * Eisen et al. (1998) Eisen, M., Spellman, P., Brown, P., and Botstein, D.  Cluster analysis and display of genome-wide expression patterns.  _Proceedings of the National Academy of Sciences of the United States of America_ , 95(25):14863–14868, December 1998.  ISSN 0027-8424.  doi: 10.1073/pnas.95.25.14863.
  * Großwendt & Röglin (2015) Großwendt, A. and Röglin, H.  Improved analysis of complete-linkage clustering.  In Bansal, N. and Finocchi, I. (eds.), _Algorithms - ESA 2015 \- 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings_ , volume 9294 of _Lecture Notes in Computer Science_ , pp. 656–667. Springer, 2015.  doi: 10.1007/978-3-662-48350-3“˙55.  URL https://doi.org/10.1007/978-3-662-48350-3_55.
  * Großwendt et al. (2019) Großwendt, A., Röglin, H., and Schmidt, M.  Analysis of ward’s method.  In Chan, T. M. (ed.), _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019_ , pp. 2939–2957. SIAM, 2019.  doi: 10.1137/1.9781611975482.182.  URL https://doi.org/10.1137/1.9781611975482.182.
  * Hennig et al. (2015) Hennig, C., Meila, M., Murtagh, F., and Rocci, R.  _Handbook of Cluster Analysis_.  Chapman and Hall/CRC, 2015.
  * Jain et al. (1999) Jain, A. K., Murty, M. N., and Flynn, P. J.  Data clustering: A review.  _ACM Comput. Surv._ , 31(3):264–323, September 1999.  ISSN 0360-0300.
  * Kleinberg & Tardos (2006) Kleinberg, J. M. and Tardos, É.  _Algorithm design_.  Addison-Wesley, 2006.  ISBN 978-0-321-37291-8.
  * Laber & Murtinho (2023) Laber, E. S. and Murtinho, L.  Optimization of inter-group criteria for clustering with minimum size constraints.  In _NeurIPS_ , 2023.
  * Lin et al. (2010) Lin, G., Nagarajan, C., Rajaraman, R., and Williamson, D. P.  A general approach for incremental approximation and hierarchical clustering.  _SIAM J. Comput._ , 39(8):3633–3669, 2010.  doi: 10.1137/070698257.  URL https://doi.org/10.1137/070698257.
  * Megiddo (1990) Megiddo, N.  On the complexity of some geometric problems in unbounded dimension.  _J. Symb. Comput._ , 10(3/4):327–334, 1990.  doi: 10.1016/S0747-7171(08)80067-3.  URL https://doi.org/10.1016/S0747-7171(08)80067-3.
  * Moseley & Wang (2023) Moseley, B. and Wang, J. R.  Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search.  _J. Mach. Learn. Res._ , 24:1:1–1:36, 2023.  URL http://jmlr.org/papers/v24/18-080.html.
  * Murtagh (1983) Murtagh, F.  A Survey of Recent Advances in Hierarchical Clustering Algorithms.  _The Computer Journal_ , 26(4):354–359, 11 1983\.  ISSN 0010-4620.  doi: 10.1093/comjnl/26.4.354.  URL https://doi.org/10.1093/comjnl/26.4.354.
  * Murtagh & Contreras (2012) Murtagh, F. and Contreras, P.  Algorithms for hierarchical clustering: an overview.  _WIREs Data Mining Knowl. Discov._ , 2(1):86–97, 2012.  doi: 10.1002/WIDM.53.  URL https://doi.org/10.1002/widm.53.
  * Ward (1963) Ward, J. H.  Hierarchical grouping to optimize an objective function.  _Journal of the American Statistical Association_ , 1963.

##  Appendix A Proof of Proposition 2.1

In this section, we present the proof of Proposition 2.1 and then we argue
that it implies that the rule employed by complete-linkage is equivalent to
the rule that chooses at each iteration the two clusters $A$ and $B$ for which
${\tt diam}(A\cup B)$ is minimum. This rule was analyzed in (Arutyunova et
al., 2023).

###### Proof.

The proof is by induction. For $j=1$, $A_{j}$ and $A^{\prime}_{j}$ are
singletons so that ${\tt diam}(A_{1}\cup A^{\prime}_{1})=dist(x,y)$, where $x$
and $y$ are the only points in $A_{1}$ and $A^{\prime}_{1}$, respectively.

We assume by induction that the result holds for every $i<j$. First we prove
that ${\tt diam}(A_{j}\cup A^{\prime}_{j})\geq{\tt diam}(A_{j-1}\cup
A^{\prime}_{j-1})$. Note that

${\tt diam}(A_{j}\cup A^{\prime}_{j})=\max\\{{\tt diam}(A_{j}),{\tt
diam}(A^{\prime}_{j}),\max\\{dist(x,y)|(x,y)\in A_{j}\times
A^{\prime}_{j}\\}\\}$ (29)

If $A_{j}=A_{j-1}\cup A^{\prime}_{j-1}$ or $A^{\prime}_{j}=A_{j-1}\cup
A^{\prime}_{j-1}$ we conclude that ${\tt diam}(A_{j}\cup
A^{\prime}_{j})\geq{\tt diam}(A_{j-1}\cup A^{\prime}_{j-1})$. Otherwise, we
have that

$\displaystyle{\tt diam}(A_{j}\cup
A^{\prime}_{j})\geq\max\\{dist(x,y)|(x,y)\in A_{j}\times
A^{\prime}_{j}\\}\geq$ $\displaystyle\max\\{dist(x,y)|(x,y)\in A_{j-1}\times
A^{\prime}_{j-1}\\}={\tt diam}(A_{j-1}\cup A^{\prime}_{j-1}),$

where the second inequality follows from the complete-linkage rule and the
last identity follows by induction.

It remains to show that

${\tt diam}(A_{j}\cup A^{\prime}_{j})=\max\\{dist(x,y)|(x,y)\in A_{j}\times
A^{\prime}_{j}\\}$ (30)

First, we consider the case where either $A_{j}=A_{j-1}\cup A^{\prime}_{j-1}$
or $A^{\prime}_{j}=A_{j-1}\cup A^{\prime}_{j-1}$. We assume w.l.o.g. that
$A_{j}=A_{j-1}\cup A^{\prime}_{j-1}$. Thus, ${\tt diam}(A_{j})={\tt
diam}(A_{j-1}\cup A^{\prime}_{j-1})\geq{\tt diam}(A^{\prime}_{j})$, where the
inequality holds because either $A^{\prime}_{j}$ is a singleton or it was
obtained by merging two clusters before the iteration $j-1$ and, in this case,
the induction hypothesis guarantees the inequality. Moreover, in this case,
cluster $A^{\prime}_{j}$ is available to be merged right before the $(j-1)$th
merge, so it follows from the complete-linkage rule that

$\max\\{dist(x,y)|(x,y)\in A^{\prime}_{j}\times
A_{j-1}\\}\geq\max\\{dist(x,y)|(x,y)\in A_{j-1}\times A^{\prime}_{j-1}\\}$
(31)

and

$\max\\{dist(x,y)|(x,y)\in A^{\prime}_{j}\times
A^{\prime}_{j-1}\\}\geq\max\\{dist(x,y)|(x,y)\in A_{j-1}\times
A^{\prime}_{j-1}\\}$ (32)

Thus,

$\displaystyle{\tt diam}(A_{j}\cup A^{\prime}_{j})\geq$ (33)
$\displaystyle\max\\{dist(x,y)|(x,y)\in A_{j}\times A^{\prime}_{j}\\}=$ (34)
$\displaystyle\max\\{dist(x,y)|(x,y)\in(A_{j-1}\cup A^{\prime}_{j-1})\times
A^{\prime}_{j}\\}\geq$ (35) $\displaystyle\max\\{dist(x,y)|(x,y)\in
A_{j-1}\times A^{\prime}_{j-1}\\}=$ (36) $\displaystyle{\tt diam}(A_{j-1}\cup
A^{\prime}_{j-1})=$ (37) $\displaystyle{\tt diam}(A_{j})\geq{\tt
diam}(A^{\prime}_{j}),$ (38)

where (35) follows from (31) and (32), while (36) follows by induction.

Therefore, (30) must hold, otherwise the inequalities (33)-(38) would
contradict (29).

If neither $A_{j}=A_{j-1}\cup A^{\prime}_{j-1}$ nor
$A^{\prime}_{j}=A_{j-1}\cup A^{\prime}_{j-1}$ we have that

$\displaystyle{\tt diam}(A_{j}\cup A^{\prime}_{j})\geq$ (39)
$\displaystyle\max\\{dist(x,y)|(x,y)\in A_{j}\times A^{\prime}_{j}\\}\geq$
(40) $\displaystyle\max\\{dist(x,y)|(x,y)\in A_{j-1}\times
A^{\prime}_{j-1}\\}=$ (41) $\displaystyle{\tt diam}(A_{j-1}\cup
A^{\prime}_{j-1})\geq$ (42) $\displaystyle\max\\{{\tt diam}(A_{j}),{\tt
diam}(A^{\prime}_{j})\\}$ (43)

Again, (30) must hold, otherwise we contradict (29). ∎

Now we show that the rule employed by complete-linkage is equivalent to the
rule that chooses at each iteration the two clusters $A$ and $B$ for which
${\tt diam}(A\cup B)$ is minimum.

We assume for the sake of reaching a contradiction that at some iteration
complete-linkage merges clusters $A$ and $B$ while there were clusters
$A^{\prime}$ and $B^{\prime}$, with ${\tt diam}(A^{\prime}\cup
B^{\prime})<{\tt diam}(A\cup B)$, that could be merged. In this case, we
conclude that ${\tt dist}_{CL}(A^{\prime},B^{\prime})\leq{\tt
diam}(A^{\prime}\cup B^{\prime})<{\tt diam}(A\cup B)={\tt dist}_{CL}(A,B),$
where the last identity follows from Proposition 2.1. However, this
contradicts the choice of complete-linkage.

##  Appendix B Proof of Lemma 4.1

The following propositions are helpful to prove Lemma 4.1. The first one
characterizes how ${\tt pure}_{t}$ evolves when two clusters are merged.

######  Proposition B.1.

Let $g$ and $g^{\prime}$ be the clusters merged at the iteration $t$ of
Algorithm 4. Then, exactly one of the following cases happen:

  1. 1.

Both $g$ and $g^{\prime}$ are non-pure. We have that ${\tt pure}_{t}(H)={\tt
pure}_{t-1}(H)$ for every family $H$ in $G$.

  2. 2.

$g$ is a pure cluster w.r.t. family $F$ and $g^{\prime}$ is non-pure. We have
that ${\tt pure}_{t}(F)={\tt pure}_{t-1}(F)-1$ and ${\tt pure}_{t}(H)={\tt
pure}_{t-1}(H)$ for every family $H\neq F$.

  3. 3.

$g^{\prime}$ is a pure cluster w.r.t. family $F^{\prime}$ and $g$ is non-pure.
We have that ${\tt pure}_{t}(F^{\prime})={\tt pure}_{t-1}(F^{\prime})-1$ and
${\tt pure}_{t}(H)={\tt pure}_{t-1}(H)$ for every family $H\neq F^{\prime}$.

  4. 4.

$g$ and $g^{\prime}$ are pure clusters w.r.t. families $F$ and $F^{\prime}$,
respectively.

Then, ${\tt pure}_{t}(F)={\tt pure}_{t-1}(F)-1$, ${\tt
pure}_{t}(F^{\prime})={\tt pure}_{t-1}(F^{\prime})-1$ and ${\tt
pure}_{t}(H)={\tt pure}_{t-1}(H)$ for every family
$H\notin\\{F,F^{\prime}\\}$.

Moreover, If ${\tt pure}_{t-1}(F)\geq 2$ and ${\tt pure}_{t-1}(F^{\prime})\geq
2$ then $g\cup g^{\prime}$ is not added to ${\cal E}$ by line 11 of Algorithm
4.

###### Proof.

We argue for each of the cases of the statement:

  1. 1.

This case holds because no pure cluster is affected when $g$ and $g^{\prime}$
are merged.

  2. 2.

In this case, $g$ does not count for ${\tt pure}_{t}(F)$, because $g$ is
merged, and $g\cup g^{\prime}$ is not a pure cluster. Thus, ${\tt
pure}_{t}(F)={\tt pure}_{t-1}(F)-1$.

  3. 3.

The proof of this case is analogous to that of item 2.

  4. 4.

If $F=F^{\prime}$ then $g\cup g^{\prime}$ is pure w.r.t. $F$. Thus, ${\tt
pure}_{t}(F)={\tt pure}_{t-1}(F)-1$ because $g$ and $g^{\prime}$ counts only
for ${\tt pure}_{t-1}(F)$ while $g\cup g^{\prime}$ just count for ${\tt
pure}_{t}(F)$.

If $F\neq F^{\prime}$ then $g\cup g^{\prime}$ is not pure. Since $g$ counts
for ${\tt pure}_{t-1}(F)$ but not for ${\tt pure}_{t}(F)$ we have ${\tt
pure}_{t}(F)={\tt pure}_{t-1}(F)-1$. By using the same reasoning we conclude
that ${\tt pure}_{t}(F^{\prime})={\tt pure}_{t-1}(F^{\prime})-1$.

If ${\tt pure}_{t-1}(F)\geq 2$ we cannot have $g\in{\cal E}$ because $g$ is
pure w.r.t. to $F$ and no cluster in ${\cal E}$ is pure with respect to $F$.
In fact, any cluster $h\in{\cal E}$ is added to ${\cal E}$ by either line 20
or line 23, or $h=h^{\prime}\cup(h-h^{\prime})$, where $h^{\prime}$ is a
cluster that was added to ${\cal E}$ by either line 20 or line 23. Since
$h^{\prime}$ is not pure w.r.t. $F$ then $h$ is not pure w.r.t. $F$. The same
reasoning shows that if ${\tt pure}_{t-1}(F^{\prime})\geq 2$, then
$g^{\prime}\notin{\cal E}$. Therefore, $g\cup g^{\prime}$ is not added to
${\cal E}$ by line 11.

∎

######  Proposition B.2.

Every family is created by Algorithm 4 containing at least two clusters.
Moreover, if $F_{C}$ is created by case (b) of Algorithm 4 at iteration $t$,
then at the beginning of this iteration exactly two families that belong to
$C$ have exactly two pure clusters and all the other families in $C$ have at
most one pure cluster.

###### Proof.

All the families created at line 3 have at least two pure clusters. We use
induction on the number of iterations.

At the beginning of iteration $1$ all connected components of $G$ have only
one family. Let $g$ and $g^{\prime}$ be the two clusters merged when $t=1$. If
a family $F_{C}$ is created (line 25) at this iteration, then the merging of
$g$ and $g^{\prime}$ must produce a connected component with two families.
Thus, we conclude that $g$ is pure with respect to a family $F$ and
$g^{\prime}$ is pure w.r.t. to a family $F^{\prime}$, with $F^{\prime}\neq F$.
Assume w.l.o.g. that $|F^{\prime}|\geq|F|$. If (a) occurs we must have $|F|=2$
and $|F^{\prime}|>2$ and if (b) occurs we must have $|F|=2$ and
$|F^{\prime}|=2$. Furthermore, If (a) occurs $F_{C}$ will have at least two
clusters, those in $F^{\prime}\setminus\\{g^{\prime}\\}$. If (b) occurs
$F_{C}$ will also have at least two clusters, $g\cup g^{\prime}$ and the pure
cluster in $(F\cup F^{\prime})\setminus\\{g,g^{\prime}\\}$ that is not added
to ${\cal E}$ by line 23. Thus, the result holds at the first iteration.

Let $t>1$. We assume by induction that the result holds for iteration $t-1$.
We analyze iteration $t$. We split the proof into two cases:

Case 1) $F_{C}$ is created due to case (a) at iteration $t$.

The definition of the case (a) assures that there is a family $F$ in the
connected component $C$ with ${\tt pure}_{t}(F)\geq 2$. Thus, the pure
clusters w.r.t. $F$ are added to $F_{C}$, so that $F_{C}$ is created with at
least two clusters.

Case 2) $F_{C}$ is created due to case (b) at iteration $t$.

The definition of case (b) assures that $|C|\geq 2$ and all families in $C$
have at most one pure cluster after the merge of iteration $t$. Moreover,
Proposition B.1 assures that at most two families have their number of pure
clusters decreased when two clusters are merged. Thus, at least $|C|-2$
families that lie in $C$ have 0 or 1 pure cluster at the beginning of
iteration $t$, otherwise, case (b) cannot occur.

We argue that exactly two families that lie in $C$ have at least 2 pure
clusters at the beginning of iteration $t$. For the sake of a contradiction,
assume that either 0 or 1 family that lies in $C$ has at least 2 pure clusters
at the beginning of iteration $t$. We consider two scenarios:

  * •

The component $C$ does exist at the beginning of $t$, that is, it was not
produced by the union of two components at iteration $t$. In this scenario,
$C$ would satisfy either case (a) or case (b) at iteration $t-1$, and $C$
would be removed from $G$. Thus, this scenario cannot occur.

  * •

The component $C$ does not exist at the beginning of $t$. In this scenario,
$C$ is the union of two connected components of $G$ at the beginning of
iteration $t$, that is, $C=C^{\prime}\cup C^{\prime\prime}$. Let us assume
$|C^{\prime}|\geq|C^{\prime\prime}|$. If $|C^{\prime}|\geq 2$, then
$|C^{\prime}|$ would satisfy either case (a) or case (b) at iteration $t-1$
and, as a consequence, would be removed from $G$; this is not possible. If
$|C^{\prime}|=|C^{\prime\prime}|=1$, then by our assumption one of these
components, say $C^{\prime}$, has a family with at most one pure cluster at
the beginning of $t$. Then by induction, $C^{\prime}$ does not correspond to a
family created at iteration $t-1$. Thus, $C^{\prime}$ satisfies case (c) at
iteration $t-1$, so that $C^{\prime}$ would be removed from $G$. Thus, this
scenario cannot occur as well.

Let $H$ and $H^{\prime}$ be the families in $C$ that have at least 2 pure
clusters at the beginning of iteration $t$. If one of them, say $H$, has more
than 2 pure clusters, then $C$ does not satisfy case (b) because we would have
${\tt pure}_{t}(H)\geq 2$. Thus, ${\tt pure}_{t-1}(H)={\tt
pure}_{t-1}(H^{\prime})=2$ and ${\tt pure}_{t-1}(H^{\prime\prime})<2$ for
every family $H^{\prime\prime}$ in $C\setminus\\{H,H^{\prime}\\}$.

It remains to show that $F_{C}$ is created with at least two clusters. Since
(b) occurs, we must have that $g$ is pure w.r.t $H$ and $g^{\prime}$ is pure
w.r.t. $H^{\prime}$. Moreover, item 4 of Proposition B.1 guarantees that
$g\cup g^{\prime}\notin{\cal E}$. Thus, $g\cup g^{\prime}$ is added to
$F_{C}$. Moreover, either $H$ or $H^{\prime}$ will have a pure cluster that is
not added to ${\cal E}$ by line 23 and, thus, this cluster will be added to
$F_{C}$. ∎

######  Proposition B.3.

Let $C$ be the connected component associated with family $F_{C}$. If $F_{C}$
is created by case (a) of Algorithm 4, then $|C|-1$ families in $C$ have a
pure cluster added to ${\cal E}$ by line 20. If $F_{C}$ is created by case (b)
of Algorithm 4, then $|C|-2$ families in $C$ have a pure cluster added to
${\cal E}$ by line 20 and one family has a pure cluster added to ${\cal E}$ by
line 23. In both cases, $C$ has exactly one family that adds no cluster to
${\cal E}$.

###### Proof.

By Proposition B.2, every family is created with at least two pure clusters.
By Proposition B.1, at each iteration the number of pure clusters in a family
either remains the same or decreases by one unit.

If $F_{C}$ is created due to case (a), then exactly $|C|-1$ families in $C$
have at most one pure cluster. Thus, all of them reach line 20 and the result
holds.

If $F_{C}$ is created due to the case (b), then Proposition B.2 guarantees
that at the beginning of the iteration in which $F_{C}$ is created, $C$ has
exactly two families, say $H$ and $H^{\prime}$, with exactly two pure clusters
and all others with at most one pure cluster. Therefore, every family in
$C-\\{H,H^{\prime}\\}$ reaches line 20 and, thus, add a cluster to ${\cal E}$.
Furthermore, exactly one family in $\\{H,H^{\prime}\\}$ adds a cluster to
${\cal E}$ in line 23. ∎

######  Proposition B.4.

The total number of clusters added to ${\cal E}$ by lines 20 and 23 of
Algorithm 4 is at most $k$.

###### Proof.

Let $m_{>1}=|\\{T^{*}_{i}|T^{*}_{i}\mbox{ has at least 2 points}\\}|$ and
$m_{1}=|\\{T^{*}_{i}|T^{*}_{i}\mbox{ has exactly 1 point}\\}|$. Initially,
$m_{1}$ clusters are added to ${\cal E}$ (line 6).

Let $D_{1},D_{2},\ldots,D_{p}$ be the trees of the forest $D$ at the end of
the Algorithm 4. Moreover, let $int(D_{i})$ and $leaves(D_{i})$ be,
respectively, the set of internal nodes and leaves of $D_{i}$. Fix an internal
node $v$ in $D_{i}$. Note that $v$ corresponds to a family $F_{C}$ for some
connected component $C$ of $G$ that has at least two families (line 26). Each
child of $v$ corresponds to a family in $C$ and by Proposition B.3 all of them
but one add a cluster to ${\cal E}$. Hence, we can associate to $v$,
$|children(v)|-1$ clusters that are added to ${\cal E}$. Thus, the number of
clusters added to ${\cal E}$ is at most

$\displaystyle p+\sum_{i=1}^{p}\left(\sum_{v\in
int(D_{i})}(|children(v)|-1)\right)=p+\sum_{i=1}^{p}\left(-|int(D_{i})|+\sum_{v\in
int(D_{i})}|children(v)|\right)=$ $\displaystyle
p+\sum_{i=1}^{p}\left(-|int(D_{i})|+|D_{i}|-1\right)=\sum_{i=1}^{p}leaves(D_{i})=|leaves(D)|=m_{>1},$

where the term $p$ is due to the roots of the trees $D_{1},\ldots,D_{p}$ since
they can also add pure clusters to ${\cal E}$.

Therefore, the total number of clusters in ${\cal E}$ never exceeds
$m_{>1}+m_{1}=k$. ∎

The next proposition characterizes the clusters created by complete-linkage.

######  Proposition B.5.

At the beginning of iteration $t$ of Algorithm 4, each cluster
$h\in\mathcal{C}^{t-1}$ satisfies exactly one of the following possibilities:

  * (i)

$h\in{\cal E}$;

  * (ii)

$h\notin{\cal E}$ and $h$ is pure w.r.t a family in $G$;

  * (iii)

$h\notin{\cal E}$, $h$ is non-pure and there is a component $C$ in $G$ such
that $h\subseteq\bigcup_{H\in C}{\tt Pts}(H)$.

###### Proof.

At the beginning of Algorithm 4, each cluster $h$ satisfies (i) or (ii). We
assume by induction that this property holds at the beginning of iteration $t$
and prove that it also holds at the beginning of iteration $t+1$.

We first argue that right after the merge of iteration $t$ every cluster in
$\mathcal{C}^{t}$ satisfies one of the desired conditions and, then, we argue
that these clusters still satisfy the desired conditions by the end of
iteration $t$ or, equivalently, at the beginning of iteration $t+1$.

Let $h$ be a cluster in $\mathcal{C}^{t}$. If $h$ also belongs to to
$\mathcal{C}^{t-1}$ then, by induction, $h$ satisfies one of the conditions at
the beginning of iteration $t$. If $h$ satisfies (i) (resp. (ii)), then it
also satisfies (i) (resp. (ii)) right after the merge because the assumption
that $h\in\mathcal{C}^{t}$ guarantees that $h$ is not merged at iteration $t$.
If $h$ satisfies (iii), then $h\subseteq\bigcup_{H\in C}{\tt Pts}(H)$, for
some connected component of $G$. Hence, $h$ satisfies the condition
$h\subseteq\bigcup_{H\in C^{new}}{\tt Pts}(H)$, after the merge, where
$C^{new}$ is the component in $G$ that contains the families of $C$ after the
merge.

If $h$ does not belong to $\mathcal{C}^{t-1}$, then $h=g\cup g^{\prime}$,
where $g$ and $g^{\prime}$ are the clusters merged at iteration $t$. If
$g\in{\cal E}$ or $g^{\prime}\in{\cal E}$ then $h\in{\cal E}$, so it satisfies
(i) after the merge. If neither $g\in{\cal E}$ nor $g^{\prime}\in{\cal E}$
then $h$ is not added to ${\cal E}$. Moreover, if both $g$ and $g^{\prime}$
are pure with respect to the same family $H$, then $h$ is also pure w.r.t.
$H$, so it satisfies (ii). Otherwise, $h$ is not pure and it satisfies (iii)
when it is created.

We have just proved that every cluster in $\mathcal{C}^{t}$ satisfies one of
the conditions of the proposition right after the merge. Now we show that each
cluster in $\mathcal{C}^{t}$ satisfies one of the conditions at the end of the
iteration $t$.

Let $h\in\mathcal{C}^{t}$. We have the following cases:

  * •

$h$ satisfies (i) after the merge. Then, it will satisfy (i) at the beginning
of iteration $t+1$.

  * •

$h$ satisfies (ii) after the merge. Then, $h$ is pure w.r.t. some family $H$.
Let $C$ be the component where the family $H$ lies. If $C$ meets the
conditions of cases (a) or (b) then $h$ will satisfy (ii) at the beginning of
iteration $t+1$. because $h$ will be pure with respect to the new family
$F_{C}$. If $C$ meets the conditions of case (c) then $h$ is added to ${\cal
E}$, so it satisfies (i) at the beginning of iteration $t+1$. If $C$ does not
meet any of the cases, then $h$ will satisfy either (i) or (ii) at the
beginning of iteration $t+1$.

  * •

$h$ satisfies (iii) after the merge. Let $C$ be a component of $G$, right
after the merge, such that $h\subseteq\bigcup_{H\in C}{\tt Pts}(H)$. Note the
$|C|\geq 2$ and, thus $C$ cannot meet case (c). If $C$ meets either case (a)
or (b) then $h$ will satisfy (ii) at the beginning of iteration $t+1$ because
$h$ will be pure with respect to the new family $F_{C}$. If $C$ does not meet
(a) or (b), then $h$ will satisfy (iii) at the beginning of iteration $t+1$.

∎

Now we state and prove two propositions that, together, directly imply the
correctness of Lemma 4.1.

######  Proposition B.6.

Every connected component $C$ in $G$ satisfies one of the following
conditions: (i) $|C|=1$ and the only family of $C$ has at least two pure
clusters or (ii) $|C|>1$ and there exist two families in $C$ such that each of
them has at least two pure clusters.

###### Proof.

For the sake of reaching a contradiction, let $t$ be the first iteration for
which there is a component $C$ in $G$ that does not satisfy the conditions of
the lemma at the beginning of iteration $t$. Note that $t\geq 2$.

If $|C|=1$ and the only family $F$ in $C$ does not have at least 2 pure
clusters, then $C$ cannot be the component associated with the family $F_{C}$
created by either case (a) or (b) at iteration $t-1$ because Proposition B.2
guarantees that the component where $F_{C}$ lies satisfies condition (i).
Thus, $C$ satisfies the condition of case (c) at iteration $t-1$ and then it
is removed from $G$ at iteration $t-1$, which contradicts its existence at the
beginning of iteration $t$

If both $|C|\geq 2$ and $C$ has only one family with at least 2 pure clusters,
then $C$ would satisfy case (a) at iteration $t-1$ and it would be removed
from $G$, which contradicts its existence at the beginning of iteration $t$.
Similarly, if $|C|\geq 2$ and it has no family with at least 2 pure clusters
then $C$ would satisfy case (b) at iteration $t-1$ and it would be removed
from $G$, which again contradicts its existence at the beginning of iteration
$t$

We have established the proposition. ∎

######  Proposition B.7.

If all the nodes/families of $G$ are removed at iteration $t^{\prime}$ then
$t^{\prime}=n-k$

###### Proof.

We first argue that at the beginning of iteration $t^{\prime}$, $G$ has
exactly one connected component. For the sake of reaching a contradiction, let
us assume that $G$ has two components say $C$ and $C^{\prime}$. By Proposition
B.6, $C$ has one family, say $F$, with ${\tt pure}_{t^{\prime}-1}(F)\geq 2$.
Let $g$ and $g^{\prime}$ be the clusters merged at iteration $t^{\prime}$. If
neither $g$ not $g^{\prime}$ is pure with respect to $F$ we will have ${\tt
pure}_{t^{\prime}}(F)\geq 2$ and the component where $F$ lies after the merge
will not satisfy the condition of case (c). Hence, there still be nodes in $G$
by the end of $t^{\prime}$. Thus, one of the clusters, say $g$, is pure w.r.t.
$F$. By using the same reasoning we conclude that $C^{\prime}$ has at least
one family, say $F^{\prime}$, with ${\tt pure}_{t^{\prime}-1}(F^{\prime})\geq
2$ and $g^{\prime}$ is pure w.r.t. $F^{\prime}$. Since $g\cup
g^{\prime}\notin{\cal E}$ (item 4 of Proposition B.1) then $g\notin{\cal E}$
and $g^{\prime}\notin{\cal E}$, so that the merge of $g$ and $g^{\prime}$ will
create a component $C\cup C^{\prime}$ in $G$ that has at least two families;
this component does not not satisfy the conditions of case (c), so $G$ will
have nodes by the end of iteration $t^{\prime}$

We have proved that if $G$ has all its nodes removed at iteration
$t^{\prime}$, then there is only one component in $G$ at the beginning of
iteration $t^{\prime}$. Let $C$ be this component: $C$ must have exactly one
family, say $F$, and $F$ must have at most two pure clusters, otherwise case
(c) is not reached and $G$ will still have nodes by the end of iteration
$t^{\prime}$.

Since $|C|=1$ no cluster satisfies condition (iii) of Proposition B.5 and,
thus, the total of clusters at the beginning of iteration $t^{\prime}$ is
given by the number of clusters that satisfy either condition (i) or (ii) of
Proposition B.5.

Proposition B.4 guarantees that the number of clusters $h\in{\cal E}$ is at
most $k$. Thus, if $F$ has less than two pure clusters at the beginning of
$t^{\prime}$, then the number of clusters $h$ that satisfies (i) or (ii) of
Proposition B.5. is at most $k+1$.

If $F$ has two pure clusters at the beginning of $t^{\prime}$ and $C$
satisfies case (c) at iteration $t^{\prime}$, then a pure cluster in $F$ is
added to ${\cal E}$. Thus, Proposition B.4 guarantees that ${\cal E}$ has at
most $k-1$ clusters at the beginning of iteration $t^{\prime}$. Hence, the
number of clusters that that satisfies (i) or (ii) of Proposition B.5 is,
again, at most $(k-1)+2=k+1$.

Thus, the total number at the beginning of iteration $t^{\prime}$ is at most
$k+1$ and, hence, $t^{\prime}=n-k$. ∎

Proof of Lemma 4.1. It follows directly from Propositions B.6 and B.7.

##  Appendix C Useful inequalities

######  Proposition C.1.

Let $p=\log_{2}3-1$ and let $a,b,x,y$ real numbers with $0\leq a,b$ and
$x,y\geq 1$. Moreover, let $ax^{p}\geq by^{p}$. Then,

$ax^{p}+2by^{p}\leq(a+b)(x+y)^{p}$

###### Proof.

Let

$f(a,b,x,y)=(a+b)(x+y)^{p}-ax^{p}-2by^{p}.$

We have that

$\frac{\partial f}{\partial a}=(x+y)^{p}-x^{p}>0.$

Since $ax^{p}\geq by^{p}$, in the minimum of $f$, we must have $a=b(y/x)^{p}$.
When $a=b(y/x)^{p}$, we have that

$f(a,b,x,y)=b\left(\left(\frac{y}{x}\right)^{p}+1)(x+y)^{p}-3by^{p}\right)=\\\
b\left((y^{p}+x^{p})(x+y)^{p}-3x^{p}y^{p}\right)$

Since $b\geq 0$ it is enough to prove that
$(y^{p}+x^{p})(x+y)^{p}-3x^{p}y^{p}\geq 0$

By the AGM inequality

$x^{p}+y^{p}\geq 2(x^{p/2})(y^{p/2})$

and

$(x+y)^{p}\geq(2(xy)^{1/2})^{p}$

By multiplying these inequalities we get

$(x^{p}+y^{p})(x+y)^{p}\geq 2^{p}2(x^{p}y^{p})=3x^{p}y^{p}$

∎

######  Proposition C.2.

The following holds

$\frac{\log 6}{\log 4}=\max\left\\{\frac{\log(2i-2)}{\log i}|i\mbox{ is an
integer larger than }1\right\\}$

###### Proof.

We can inspect manually that $\log(2i-2)/\log i\leq\frac{\log 6}{\log 4},$ for
every integer smaller than 11. For $i\geq 11$ we have that

$\frac{\log(2i-2)}{\log i}<\frac{\log(2i)}{\log i}=1+\frac{1}{\log i}\leq
1+\frac{1}{\log 11}\leq\frac{\log 6}{\log 4}$

. ∎

######  Proposition C.3.

Let $p$ be a real number that satisfies $p\geq\log_{i}(2i-2),$ for every
$i>1$. Moreover, let $\ell$ be a positive number larger than 1 and let $1\leq
a_{1}\leq a_{2}\ldots\leq a_{\ell}$. Then,

$a_{\ell}^{p}+a_{\ell-1}^{p}+\sum_{i=1}^{\ell-2}2a_{i}^{p}\leq\left(\sum_{i=1}^{\ell}a_{i}\right)^{p}$

###### Proof.

Let $\mathbf{a}=(a_{1},\ldots,a_{\ell})$. We define

$f(\mathbf{a}):=\left(\sum_{i=1}^{\ell}a_{i}\right)^{p}-\left(a_{\ell}^{p}+a_{\ell-1}^{p}+\sum_{i=1}^{\ell-2}2a_{i}^{p}\right).$

We need to show that $f(\mathbf{a})\geq 0$, for every valid $\mathbf{a}$.

First, we consider the case $\ell=2$. In this case,

$\frac{\partial f}{\partial a_{2}}=p(a_{1}+a_{2})^{p-1}-pa_{2}^{p-1}>0$

Thus, in the minimum of $f$ we must have $a_{1}=a_{2}$. When this happens,

$f(\mathbf{a})=(2a_{1})^{p}-2a_{1}^{p}>0.$

Now, we consider the case $\ell>2$. For $t\leq\ell-2$, we define

$f^{t}(\mathbf{a}):=\left(\sum_{i=1}^{t-1}a_{i}+(\ell-t+1)a_{t}\right)^{p}-\left(2(\ell-t)a_{t}^{p}+\sum_{i=1}^{t-1}2a_{i}^{p}\right)$

Note that $f^{t}(\mathbf{a})=f(\mathbf{a}^{\prime})$ where
$a^{\prime}_{i}=a_{i}$ for $i<t$ and $a^{\prime}_{i}=a_{t}$ for $i\geq t$. We
show that the minimum of $f$ is equal to the minimum of $f^{t}$.

For $j>\ell-2$,

$\frac{\partial f}{\partial
a_{j}}=p(\sum_{i=1}^{\ell}a_{i})^{p-1}-pa_{j}^{p-1}>0.$

Hence, in the minimum of $f$ we have that $a_{\ell-2}=a_{\ell-1}=a_{\ell}$.
Thus, the minimum of $f$ equals the minimum of $f^{\ell-2}$. Now, we show that
the minimum of $f^{t}$ is equal to the minimum of $f^{t-1}$ for $t\leq\ell-2$.

We have that

$\displaystyle\frac{\partial f^{t}}{\partial
a_{t}}=(\ell-t+1)p\left(\sum_{i=1}^{t-1}a_{i}+(\ell-t+1)a_{t}\right)^{p-1}-2(\ell-t)pa_{t}^{p-1}>$
$\displaystyle p(\ell-t+1)^{p}a_{t}^{p-1}-2(\ell-t)pa_{t}^{p-1}\geq$
$\displaystyle 0,$

where the second inequality holds because the definition of $p$ assures that
$p\geq\frac{\log 2(\ell-t)}{\log(\ell-t+1)}.$ Hence, in the minimum of $f^{t}$
we have that $a_{t}=a_{t-1}$, so that the minimum of $f^{t}$ equal the minimum
of $f^{t-1}$. Therefore, we can conclude that the minimum of $f$ is equal to
the minimum of $f^{1}$.

Now we note that

$f^{1}(\mathbf{a})=(\ell
a_{1})^{p}-(2\ell-2)(a_{1})^{p}\geq(2\ell-2)(a_{1})^{p}-(2\ell-2)(a_{1})^{p}=0,$

where the inequality holds because $p\geq\log_{\ell}(2\ell-2)$ ∎