an approximation guarantee of $8$ for the discrete $k$-center problem is known [@dasgupta]. This implies an algorithm with an approximation guarantee of $16$ for the diameter $k$-clustering problem.

This paper as well as all of the above mentioned work is about static clustering, i.e. in the problem definition we are given the whole set of input points at once. An alternative model of the input data is to consider sequences of points that are given one after another. In [@charikar], the authors discuss clustering in a so-called *incremental clustering* model. They give an algorithm with constant approximation factor that maintains a hierarchical clustering while new points are added to the input set. Furthermore, they show a lower bound of $\Omega(\log k)$ for the agglomerative complete linkage algorithm and the diameter $k$-clustering problem. However, since their model differs from ours, their results have no bearing on our results.

Our contribution
----------------

In this paper, we study the agglomerative complete linkage clustering algorithm and related algorithms for input sets $X\subset{\mathbb{R}}^d$. To measure the distance between data points, we use a metric that is based on a norm, e.g., the Euclidean metric. We prove that the agglomerative solution to the diameter $k$-clustering problem 