In computational geometry, a well-separated pair decomposition (WSPD) of a set of points S ⊂ R d {\displaystyle S\subset \mathbb {R} ^{d}} , is a sequence of pairs of sets ( A i , B i ) {\displaystyle (A_{i},B_{i})} , such that each pair is well-separated, and for each two distinct points p , q ∈ S {\displaystyle 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
Let A , B {\displaystyle A,B} be two disjoint sets of points in R d {\displaystyle \mathbb {R} ^{d}} , R ( X ) {\displaystyle R(X)} denote the axis-aligned minimum bounding box for the points in X {\displaystyle X} , and s > 0 {\displaystyle s>0} denote the separation factor. We consider A {\displaystyle A} and B {\displaystyle B} to be well-separated, if for each of R ( A ) {\displaystyle R(A)} and R ( B ) {\displaystyle R(B)} there exists a d-ball of radius ρ {\displaystyle \rho } containing it, such that the two spheres have a minimum distance of at least s ρ {\displaystyle s\rho } . We consider a sequence of well-separated pairs of subsets of S {\displaystyle S} , ( A 1 , B 1 ) , ( A 2 , B 2 ) , … , ( A m , B m ) {\displaystyle (A_{1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})} to be a well-separated pair decomposition (WSPD) of S {\displaystyle S} if for any two distinct points p , q ∈ S {\displaystyle p,q\in S} , there exists precisely one i {\displaystyle i} , 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m} , such that either
p ∈ A i {\displaystyle p\in A_{i}} and q ∈ B i {\displaystyle q\in B_{i}} , or
q ∈ A i {\displaystyle q\in A_{i}} and p ∈ B i {\displaystyle 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 ) {\displaystyle O(s^{d}n)} in O ( n lg n ) {\displaystyle O(n\lg n)} time. 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 v and w as, respectively, the left and right children of u. R(u) := R(S) return u
… excerpt ends here. Continue reading the full article.
