# Complexity of clustering lattice points

[Note] I have completely rewrited the question after Yuval's comments. I hope it makes more sense now!

$\newcommand\ZZ{\mathbb Z}$$\newcommand\dist{\operatorname{dist}}$Consider the $d$-dimensional integer lattice $\ZZ^d$, equipped with the max distance $\dist$: for $s=(s_1,\dotsc,s_d)$ and $s'=(s'_1, \dotsc, s'_d)$, $\dist(s,s')=\max_{1\le t\le d} |s_t-s'_t|$. We extend $\dist$ to sets of points as follows: $\dist(S,S') = \min_{(s,s')\in S\times S'} \dist(s,s')$.

Definition. Given $\delta\in\ZZ_+$, a set $S\subset\ZZ^d$ of points is a $\delta$-cluster if for all $s,s'\in S$, there exist $s^1=s$, $s^2$, ..., $s^p=s'$ such that $\dist(s^r,s^{r+1})\le\delta$ for $1\le r< p$.

Here is the problem I am interested in:

$\text{Cluster}(S,\delta)$:
Input: A set $S\subset\ZZ^d$ and a distance $\delta\in\ZZ_+$;
Output 1: A partition $S=S_1\sqcup \dotsb\sqcup S_k$ such that each $S_i$ is a $\delta$-cluster and for all $i\neq j$, $\dist(S_i,S_j)>\delta$.
Output 2: A list of $(k-1)$ couples $[(i_1,j_1),\dotsc,(i_{k-1},j_{k-1})]$, $i_s<j_s$ for $1\le s\le k-1$, such that:

• $S_{i_1}$ and $S_{j_1}$ are the closest clusters: $\dist(S_{i_1},S_{j_1}) = \min_{i,j\in\{1,\dotsc,k\}} \dist(S_i,S_j)$;
• If $S_{i_1}$ and $S_{j_1}$ are merged, $S_{i_2}$ and $S_{j_2}$ are the closest remaining clusters: $\dist(S_{i_2},S_{j_2})=\min_{i,j\in\{1,\dotsc,k\}\setminus\{j_1\}} \dist(S_i,S_j)$, where $S_{i_1}$ has been replaced by $S_{i_1}\cup S_{j_1}$;
• ...
• $S_{i_{k-1}}$ and $S_{j_{k-1}}$ are the last two clusters to be merged.
1. What is the complexity of (each step of) $\text{Cluster}(S,\delta)$, with respect to $|S|$, $d$, $\delta$ and $N=\max_{s\in S} \|s\|_\infty$?

• I am mostly interested in the case $d\ll |S|$ and in the dependence on $|S|$.
• One can define from $S$ a graph $G_S=(S,E)$ where $(s,s')\in E$ iff $\dist(s,s')\le\delta$. The graph $G_S$ can be constructed in quadratic time in $|S|$, and the partition is the partition of $S$ into connected components. Can we do better than quadratic time, maybe not constructing the whole graph? And once the partition is computed, what is the complexity of updating it?
2. For $\delta\in\ZZ_+^d$, we now define a $\delta$-cluster to be a set $S$ of points such that for all $s,s'\in S$, $|s_t-s'_t|\le\delta_t$ for $1\le t\le d$. This allows to construct a graph $G_S$ as above. Does the complexity change with this new measure of distance?

Final remarks.

• I am mostly interested in the deterministic complexity of these problems, though any result may be of interest (probabilistic algorithm, fast algorithm in practice, and maybe most used algorithms for these problems, if they are as classic as I guess).
• In the literature, all the references I find deal with the problem of finding $k$ clusters, where $k$ is an input of the problem rather than the threshold distance $\delta$.
• If one takes the graph approach, there is some literature on updating connected components when edges are added. Though I suspect that this approach cannot do better than $O(|S|^2)$ while ideally I would like to be able to have a subquadratic algorithm.
• Regarding the first problem: (1) It doesn't always have a solution; (2) The running time of any algorithm will depend on $|S|$, unless you assume all points are distinct (but then you get really bad estimates); (3) There is a trivial $O(|S|^2) = O(N)^{2d}$ algorithm, though you can probably do better. Apr 18, 2015 at 14:54
• @YuvalFilmus: Thanks for your comment! (1) Why? Maybe I am unclear, but two points belong to the same $S_i$ iff they are at distance $\le\delta$. I cannot see why there may be no solution! (2) Of course! I'll correct. (3) Agreed ;-) Apr 18, 2015 at 16:52
• Take $d=1$, $\delta = 1$ and the points $0,1,2$. Apr 18, 2015 at 18:42
• Right... I have to think more about my problem to get the correct formulation. Apr 18, 2015 at 18:48