# Complexity for single-linkage clustering with max norm

Let $S\in\mathbb Z^d$ be a set of points, with some notion of distance $d(x,y)$ between two points $x,y\in S$. I am specifically interested in the max distance, that is $d(x,y)=\max_{1\le i\le d} |x_i-y_i|$ where $x=(x_1,\dotsc,x_d)$ and $y=(y_1,\dotsc,y_d)$.

Single-linkage clustering consists in computing a tree $T$ on the set $S$ of minimal distances, that can be defined by the following algorithm that computes the set $E$ of edges of $T$ as follows:

1. Set $E=\emptyset$ [each point is a cluster]
2. While $|E|<|S|-1$, add to $E$ a pair $(x,y)$ such that
• $x$ and $y$ are in distinct connected components of $T$;
• $d(x,y) = min_{u,v} d(u,v)$ where the minimum is taken over all pairs of points $u$, $v$ that are in distinct connected components of $T$.

If one first computes all the distances between pairs of points in $S$ and sort them, the above algorithms allows to compute the tree $T$ in time $\tilde O(n^2)$ if one assumes that the distance can be computed in time $O(1)$. Here the notation $\tilde O(\cdot)$ hides poly-logarithmic factors.

What is the complexity of computing this tree, when the distance is the max distance?

• If $d=2$, is there a quasi-linear algorithm (that is in time $\tilde O(n)$)?
• More generally, if $d$ is fixed, is there a quasi-linear algorithm?
• Or is there a quadratic lower bound (in some reasonable model)?

Note: I asked a similar question some days ago on cs.sx. I had no answer, so I re-post it here with a new (and I guess better) formulation.

Single-linkage clustering gives the same connections in the same order that you would find using Kruskal's algorithm for the minimum spanning tree, and the clustering can be found by finding a minimum spanning tree and then running Kruskal's algorithm on the resulting $(n-1)$-edge graph. Therefore, the time is bounded by the MST construction + the time to sort the edges of the MST.
The two-dimensional $L^\infty$ MST can be constructed in $O(n\log n)$ time using rectilinear Voronoi diagrams, and an $O(n\log n)$ algorithm for the three-dimensional version is given by
Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999), Minimum spanning trees in $d$ dimensions, Nordic J. Comput. 6 (4): 446–461.