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:


Set $E=\emptyset$ [each point is a cluster]
While $|E|&lt;|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. 

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