Well-separated pair decomposition

In computational geometry, a well-separated pair decomposition (WSPD) of a set of points $S\subset {ℝ}^d$, is a sequence of pairs of sets $(A_i,B_i)$, such that each pair is well-separated, and for each two distinct points $p,q\in S$, there exists precisely one pair which separates the two.

The graph induced by a well-separated pair decomposition can serve as a k-spanner of the complete Euclidean graph, and is useful in approximating solutions to several problems pertaining to this.

Definition

Visual representation of well-separated pair

Let $A,B$ be two disjoint sets of points in ${ℝ}^d$, $R(X)$ denote the axis-aligned minimum bounding box for the points in $X$, and $s>0$ denote the separation factor.

We consider $A$ and $B$ to be well-separated, if for each of $R(A)$ and $R(B)$ there exists a d-ball of radius $\rho$ containing it, such that the two spheres have a minimum distance of at least $s\rho$.

We consider a sequence of well-separated pairs of subsets of $S$, $(A_1,B_1),(A_2,B_2),\dots ,(A_m,B_m)$ to be a well-separated pair decomposition (WSPD) of $S$ if for any two distinct points $p,q\in S$, there exists precisely one $i$, $1\le i\le m$, such that either

• $p\in A_i$ and $q\in B_i$, or
• $q\in A_i$ and $p\in B_i$.

Construction

Split tree

By way of constructing a fair split tree, it is possible to construct a WSPD of size $O(s^{d}n)$ in $O(n\lg n)$ time.

The general principle of the split tree of a point set Template:Math is that each node Template:Math of the tree represents a set of points Template:Math and that the bounding box Template:Math of Template:Math is split along its longest side in two equal parts which form the two children of Template:Math and their point set. It is done recursively until there is only one point in the set.

Let Template:Math denote the size of the longest interval of the bounding hyperrectangle of point set Template:Math and let Template:Math denote the size of the i-th dimension of the bounding hyperrectangle of point set Template:Math. We give pseudocode for the Split tree computation below.

Template:Math
    Let Template:Math be the node for Template:Math
    if Template:Math
        Template:Math // Template:Math is a hyperrectangle which each side has a length of zero.
        Store in Template:Math the only point in S.
    else
        Compute Template:Math
        Let the i-th dimension be the one where Template:Math
        Split Template:Math along the i-th dimension in two same-size hyperrectangles and take the points contained in these hyperrectangles to form the two sets Template:Math and Template:Math.
        Template:Math
        Template:Math
        Store Template:Math and Template:Math as, respectively, the left and right children of Template:Math.
        Template:Math
    return Template:Math

This algorithm runs in $O(n^2)$ time.

We give a more efficient algorithm that runs in $O(n\lg n)$ time below. The goal is to loop over the list in only $O(n)$ operations per step of the recursion but only call the recursion on at most half the points each time.

Let Template:Math be the i-th coordinate of the j-th point in Template:Math such that Template:Math is sorted according to the i-th coordinate and Template:Math be the point. Also, let Template:Math be the hyperplane that splits the longest side of Template:Math in two. Here is the algorithm in pseudo-code:

Template:Math
    if Template:Math
        Template:Math // Template:Math is a hyperrectangle which each side has a length of zero.
        Store in Template:Math the only point in Template:Math.
    else
        Template:Math
        repeat
            Compute Template:Math
            Template:Math
            Template:Math
            Template:Math
            Let the i-th dimension be the one where Template:Math
            Template:Math
            Template:Math
            while Template:Math and Template:Math
                Template:Math
                Template:Math}
                Template:Math}
                Template:Math
                Template:Math
            
            Let Template:Math and Template:Math be respectively, the left and right children of Template:Math.
            if Template:Math
                Template:Math
                Template:Math
                Template:Math
                Template:Math
            else if Template:Math
                Template:Math
                Template:Math
                Template:Math
                Template:Math
        until Template:Math
        Template:Math

To be able to maintain the sorted lists for each node, linked lists are used. Cross-pointers are kept for each list to the others to be able to retrieve a point in constant time. In the algorithm above, in each iteration of the loop, a call to the recursion is done. In reality, to be able to reconstruct the list without the overhead of resorting the points, it is necessary to rebuild the sorted lists once all points have been assigned to their nodes. To do the rebuilding, walk along each list for each dimension, add each point to the corresponding list of its nodes, and add cross-pointers in the original list to be able to add the cross-pointers for the new lists. Finally, call the recursion on each node and his set.

WSPD computation

Visual representation of a well-separated pair computed with the bounding boxes

The WSPD can be extracted from such a split tree by calling the recursive Template:Math function on the children of every node in the split tree. Let Template:Math / Template:Math denote the children of the node Template:Math. We give pseudocode for the Template:Math function below.

FindWSPD(T, s)
    for each node u that is not a leaf in the split tree T do
        FindPairs(ul, ur)

We give pseudocode for the Template:Math function below.

FindPairs(v, w)
    if Template:Math and Template:Math are well-separated with respect to Template:Math 
        report Template:Math
    else
        if( Template:Math )
            Recursively call Template:Math and Template:Math
        else
            Recursively call Template:Math and Template:Math

Combining the Template:Math-well-separated pairs from all the calls of Template:Math gives the WSPD for separation Template:Math.

Template:Collapse top It is clear that the pairs returned by the algorithm are well-separated because of the return condition of the function Template:Math.

Now, we have to prove that for any distinct points $p$ and $q$ in $S$, there is a unique pair $\{A,B\}$ so that (i) $p\in A$ and $q\in B$ or (ii) $p\in B$ and $q\in A$. Assume without loss of generality that (i) holds.

Let $u$ be the lowest common ancestor of $p$ and $q$ in the split tree and let $v$ and $w$ be the children of $u$. Because of the last assumption, $p$ is in the subtree of $v$ and $q$ in the subtree of $w$. A call to Template:Math is necessarily done in Template:Math. Because, each time there is a recursion, the recursion tree creates two branches that contain all the points of the current recursion call, there will be a sequence of call to Template:Math leading to having $p$ in $A$ and $q$ in $B$.

Because $u$ is the lowest common ancestor of $p$ and $q$, calling Template:Math on the children of a higher node would result of $p$ and $q$ not being in a pair and calling Template:Math on the children in one of the nodes of one of the subtrees of $u$ would result by $p$ or $q$ not being in any pair. Thus, the pair $\{A,B\}$ is the unique one separating $p$ and $q$. Template:Collapse bottom

Each time the recursion tree split in two, there is one more pair added to the decomposition. So, the algorithm run-time is in the number of pairs in the final decomposition.

Callahan and Kosaraju proved that this algorithm finds a Well-separated pair decomposition (WSPD) of size $O(s^{d}n)$.

Properties

Lemma 1: Let $\{A,B\}$ be a well-separated pair with respect to $s$. Let $p,p^{\prime }\in A$ and $q\in B$. Then, $|p{p}^{\prime }|\le (2/s)|pq|$.

Proof: Because $p$ and $p^{\prime }$ are in the same set, we have that $|p{p}^{\prime }|\le 2\rho$ where $\rho$ is the radius of the enclosing circle of $A$ and $B$. Because $p$ and $q$ are in two well-separated sets, we have that $|pq|\ge s\rho$. We obtain that:

$\begin{array}{cc}& \frac{|p{p}^{\prime }|}{2}\le \rho \le \frac{|pq|}{s}\\ \iff & \\ & \frac{|p{p}^{\prime }|}{2}\le \frac{|pq|}{s}\\ \iff & \\ & |p{p}^{\prime }|\le \frac{2}{s}|pq|\\ \end{array}$

Lemma 2: Let $\{A,B\}$ be a well-separated pair with respect to $s$. Let $p,p^{\prime }\in A$ and $q,q^{\prime }\in B$. Then, $|p^{\prime }{q}^{\prime }|\le (1+4/s)|pq|$.

Proof: By the triangle inequality, we have:

$|p^{\prime }{q}^{\prime }|\le |p^{\prime }p|+|pq|+|q{q}^{\prime }|$

From Lemma 1, we obtain:

$\begin{array}{cc}|p^{\prime }{q}^{\prime }|& \le (2/s)|pq|+|pq|+(2/s)|pq|\\ & =(1+4/s)|pq|\end{array}$

Applications

The well-separated pair decomposition has application in solving a number of problems. WSPD can be used to:

• Solve the closest pair problem in $O(n\lg n)$ time.
• Solve the k-closest pairs problem in $O(n\lg n+k)$ time.
• Solve the k-closest pair problem in $O(n\lg n)$ time.
• Solve the all-nearest neighbors problem in $O(n\lg n)$ time.
• Provide a $(1-ϵ)$-approximation of the diameter of a point set in $O(n\lg n)$ time.
• Directly induce a t-spanner of a point set.
• Provide a t-approximation of the Euclidean minimum spanning tree in d dimensions in $O(n\lg n)$ time.
• Provide a $(1+ϵ)$-approximation of the Euclidean minimum spanning tree in d dimensions in $O(n\lg n+({ϵ}^{-2}{\lg }^2\frac{1}{ϵ})n)$ time.