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.


1 Answer 1


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.

more generally an algorithm that is within a polylog factor of linear for any fixed dimension is given by

Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), Scaling and related techniques for geometry problems, Proc. 16th ACM STOC, pp. 135–143, doi:10.1145/800057.808675


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.