![]() | ||
In computational geometry, a well-separated pair decomposition (WSPD) of a set of points
Contents
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
We consider
We consider a sequence of well-separated pairs of subsets of
Split tree
By way of constructing a fair split tree, it is possible to construct a WSPD of size
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. It is done recursively until there is only one point in the 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.
SplitTree(S) Let u be the node for S if |S| = 1 R(u) := R(S) // R(S) is a hyperrectangle which each side has a length of zero. Store in u the only point in S. else Compute R(S) Let the i-th dimension be the one where Lmax(R(S)) = Li(R(S)) Split R(S) along the i-th dimension in two same-size hyperrectangles and take the points contained in these hyperrectangles to form the two sets Sv and Sw. v := SplitTree(Sv) w := SplitTree(Sw) Store w and w as, respectively, the left and right children of u. R(u) := R(S) return uThis algorithm runs in
We give a more efficient algorithm that runs in
Let Sij be the j-th coordinate of the i-th point in S such that S is sorted for each dimension and p(Sij) be the point. Also, let h(R(S)) be the hyperplane that splits the longest side of R(S) in two. Here is the algorithm in pseudo-code:
SplitTree(S, u) if R(u) := R(S) // R(S) is a hyperrectangle which each side has a length of zero. Store in u the only point in S. else size := |S| repeat Compute R(S) R(u) := R(S) j : = 1 k : = |S| Let the i-th dimension be the one where Lmax(R(S)) = Li(R(S)) Sv : = ∅ Sw : = ∅ while Sij+1 < h(R(S)) and Sik-1 > h(R(S)) size := size - 1 Sv : = Sv ∪ {p(S_i^j)} Sw : = Sw ∪ {p(S_i^k)} j := j + 1 k := k - 1 Let v and w be respectively, the left and right children of u. if Sij+1 > h(R(S)) Sw := S \ Sv u := w S := Sw SplitTree(Sv,v) else if Sik-1 < h(R(S)) Sv := S \ Sw u := v S := Sv SplitTree(Sw,w) until size ≤ n⁄2 SplitTree(S,u)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 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.
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 FindPairs(v,w) function below.
FindPairs(v,w) if Sv and Sw are well-separated with respect to s report pair(Sv,Sw) else if( Lmax(R(v)) ≤ Lmax(R(w)) ) Recursively call FindPairs(v,wl) and FindPairs(v,wr) else Recursively call FindPairs(vl,w) and FindPairs(vr,w)Combining the s-well-separated pairs from all the calls of FindPairs(v,w) gives the WSPD for separation s.
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
Properties
Lemma 1: Let
Proof: Because
Lemma 2: Let
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: