based on the $\ell_\infty$-norm, we provide a lower bound that exceeds the upper bound for $d=1$. For $d\geq3$, we give a lower bound for the Euclidean case which is larger than the lower bound for $d=1$. Finally, we construct instances providing lower bounds for any metric based on an $\ell_p$-norm with $1\leq p\leq\infty$. However, the construction of these instances needs the dimension to depend on $k$.

Preliminaries and problem definitions
=====================================

Throughout this paper, we consider input sets that are finite subsets of ${\mathbb{R}}^d$. Our results hold for arbitrary metrics that are based on a norm, i.e., the distance $\|x-y\|$ between two points $x,y\in{\mathbb{R}}^d$ is measured using an arbitrary norm $\|\cdot\|$. Readers who are not familiar with arbitrary metrics or are only interested in the Euclidean case, may assume that $\|\cdot\|_2$ is used, i.e. $\|x-y\|=\sqrt{\sum_{i=1}^d(x_i-y_i)^2}$. For $r\in{\mathbb{R}}$ and $y\in{\mathbb{R}}^d$, we denote the closed $d$-dimensional ball of radius $r$ centered at $y$ by $\operatorname{B}_r^d(y):=\left\{x\,|\,\|x-y\|\leq r\right\}$.

Given $k\in{\mathbb{N}}$ and a finite set $X\subset{\mathbb{R}}^d$ with $k\leq|X|$, we say that ${\mathcal{C}}_k=\{C_1,\ldots,C_k\}$ is a $k$-clustering of $X$ if the sets $C_1,\ldots,C_k$ (called clusters) form a partition of $X$ into $k$ non-empty subsets. We call a collection of $k$-clusterings of the same finite set $X$ but 