Well-separated pair decomposition


In computational geometry, a well-separated pair decomposition of a set of points, is a sequence of pairs of sets, 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.

Definition

Let be two disjoint sets of points in, denote the axis-aligned minimum bounding box for the points in, and denote the separation factor.
We consider and to be well-separated, if for each of and there exists a d-ball of radius containing it, such that the two spheres have a minimum distance of at least.
We consider a sequence of well-separated pairs of subsets of, to be a well-separated pair decomposition of if for any two distinct points, there exists precisely one,, such that either

Split tree

By way of constructing a fair split tree, it is possible to construct a WSPD of size in time.
The general principle of the split tree of a point set is that each node of the tree represents a set of points and that the bounding box of is split along its longest side in two equal parts which form the two children of and their point set. It is done recursively until there is only one point in the set.
Let denote the size of the longest interval of the bounding hyperrectangle of point set and let denote the size of the i-th dimension of the bounding hyperrectangle of point set. We give pseudocode for the Split tree computation below.
Let be the node for
if
// is a hyperrectangle which each side has a length of zero.
Store in the only point in S.
else
Compute
Let the i-th dimension be the one where
Split along the i-th dimension in two same-size hyperrectangles and take the points contained in these hyperrectangles to form the two sets and.


Store and as, respectively, the left and right children of.

return
This algorithm runs in time.
We give a more efficient algorithm that runs in time below. The goal is to loop over the list in only operations per step of the recursion but only call the recursion on at most half the points each time.
Let be the j-th coordinate of the i-th point in such that is sorted for each dimension and be the point. Also, let be the hyperplane that splits the longest side of in two. Here is the algorithm in pseudo-code:
if
// is a hyperrectangle which each side has a length of zero.
Store in the only point in.
else

repeat
Compute



Let the i-th dimension be the one where


while and






Let and be respectively, the left and right children of.
if




else if




until

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

The WSPD can be extracted from such a split tree by calling the recursive function on the children of every node in the split tree. Let / denote the children of the node. We give pseudocode for the function below.
for each node that is not a leaf in the split tree do

We give pseudocode for the function below.
if and are well-separated with respect to
report
else
if
Recursively call and
else
Recursively call and
Combining the -well-separated pairs from all the calls of gives the WSPD for separation.
It is clear that the pairs returned by the algorithm are well-separated because of the return condition of the function.
Now, we have to prove that for any distinct points and in, there is a unique pair so that and or and. Assume without loss of generality that holds.
Let be the lowest common ancestor of and in the split tree and let and be the children of. Because of the last assumption, is in the subtree of and in the subtree of. A call to is necessarily done in. 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 leading to having in and in.
Because is the lowest common ancestor of and, calling on the children of a higher node would result of and not being in a pair and calling on the children in one of the nodes of one of the subtrees of would result by or not being in any pair. Thus, the pair is the unique one separating and.
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 of size.

Properties

Lemma 1: Let be a well-separated pair with respect to. Let and. Then,.
Proof: Because and are in the same set, we have that where is the radius of the enclosing circle of and. Because and are in two well-separated sets, we have that. We obtain that:
Lemma 2: Let be a well-separated pair with respect to. Let and. Then,.
Proof: By the triangle inequality, we have:
From Lemma 1, we obtain:

Applications

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