<p>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.</p>

<p>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</p>

<p>Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999),
Minimum spanning trees in $d$ dimensions,
<em>Nordic J. Comput.</em> 6 (4): 446–461. </p>

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

<p>Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), Scaling and related techniques for geometry problems, <em>Proc. 16th ACM STOC</em>, pp. 135–143, <a href="http://doi.org/10.1145/800057.808675" rel="nofollow">doi:10.1145/800057.808675</a></p>

CC BY-SA 3.0
2015-04-23T15:43:39.090Z
2015-04-23T15:49:37.190Z
2015-04-23T15:49:37.190Z
David Eppstein
<p>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 <em>max distance</em>, 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)$.</p>

<p><a href="http://en.wikipedia.org/wiki/Single-linkage_clustering" rel="nofollow noreferrer">Single-linkage clustering</a> consists in computing a tree $T$ on the set $S$ of <em>minimal distances</em>, that can be defined by the following algorithm that computes the set $E$ of edges of $T$ as follows:</p>

<ol>
<li>Set $E=\emptyset$ <em>[each point is a cluster]</em></li>
<li>While $|E|&lt;|S|-1$, add to $E$ a pair $(x,y)$ such that

<ul>
<li>$x$ and $y$ are in distinct connected components of $T$;</li>
<li>$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$.</li>
</ul></li>
</ol>

<p>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.</p>

<blockquote>
  <p>What is the complexity of computing this tree, when the distance is the max distance?</p>
  
  <ul>
  <li>If $d=2$, is there a quasi-linear algorithm (that is in time $\tilde O(n)$)?</li>
  <li>More generally, if $d$ is fixed, is there a quasi-linear algorithm?</li>
  <li>Or is there a quadratic lower bound (in some <em>reasonable</em> model)?</li>
  </ul>
</blockquote>

<p><em>Note: I asked a <a href="https://cs.stackexchange.com/questions/41528/complexity-of-clustering-lattice-points">similar question</a> some days ago on cs.sx. I had no answer, so I re-post it here with a new (and I guess better) formulation.</em></p>

<reference-request><computational-geometry>
Complexity for single-linkage clustering with max norm
Bruno
# Complexity for single-linkage clustering with max norm

(Asked by: username_0 on 2015-04-23)

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](http://en.wikipedia.org/wiki/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](https://cs.stackexchange.com/questions/41528/complexity-of-clustering-lattice-points) some days ago on cs.sx. I had no answer, so I re-post it here with a new (and I guess better) formulation.*

**Tags:** reference-request, computational-geometry

---

## 1 answers

### Answer by username_1 on 2015-04-23. Score: 4 | Accepted answer

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](http://doi.org/10.1145/800057.808675)


---

