Well-separated pair decomposition

In computational geometry, a well-separated pair decomposition (WSPD) of a set of points

, such that each pair is well-separated, and for each two distinct points

, 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.

denote the axis-aligned minimum bounding box for the points in

[2] We consider a sequence of well-separated pairs of subsets of

to be a well-separated pair decomposition (WSPD) of

[2] The general principle of the split tree of a point set S is that each node u of the tree represents a set of points Su and that the bounding box R(Su) of Su is split along its longest side in two equal parts which form the two children of u and their point set.

Let Lmax(R(X)) denote the size of the longest interval of the bounding hyperrectangle of point set X and let Li(R(X)) denote the size of the i-th dimension of the bounding hyperrectangle of point set X.

We give pseudocode for the Split tree computation below.

We give a more efficient algorithm that runs in

Let Sij be the i-th coordinate of the j-th point in S such that Si is sorted according to the i-th coordinate and p(Sij) be the point.

Also, let h(R(S)) be the hyperplane that splits the longest side of R(S) in two.

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.

Finally, call the recursion on each node and his set.

The WSPD can be extracted from such a split tree by calling the recursive FindPairs(v,w) function on the children of every node in the split tree.

Let ul / ur denote the children of the node u.

We give pseudocode for the FindWSPD(T, s) function below.

We give pseudocode for the FindPairs(v, w) function below.

Combining the s-well-separated pairs from all the calls of FindPairs(v,w) gives the WSPD for separation s. It is clear that the pairs returned by the algorithm are well-separated because of the return condition of the function FindPairs.

Assume without loss of generality that (i) holds.

A call to FindPairs(v,w) is necessarily done in FindWSPD.

, calling FindPairs on the children of a higher node would result of

not being in a pair and calling FindPairs on the children in one of the nodes of one of the subtrees of

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

The well-separated pair decomposition has application in solving a number of problems.