Well-separated pair decomposition

In computational geometry, a well-separated pair decomposition of a set of points $S \subset \mathbb{R}^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.^[1]

Definition

Let $A, B$ be two disjoint sets of points in $\mathbb{R}^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 there for each of $R(A)$ and $R(B)$ exists a d-ball of radius $\rho$ containing it, such that the two spheres have a minimum distance of at least $s \rho$ .^[2]

We consider a sequence of well-separated pairs of subsets of $S$ , $(A_1, B_1), (A_2, B_2), \ldots, (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 \leq i \leq m$ , such that either

$p \in A_i$ and $q \in B_i$ , or
$q \in A_i$ and $p \in B_i$ .^[1]

Construction

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.^[2]

The split tree of a point set S is defined recursively.

If S contains only one point

Tree(S) is a single node split tree containing this one point.

If S has more than one point

Consider the bounding hyperrectangle R(S) of point set S
Split R(S) over its longest interval and divide the points according to this split into the subsets S₁ and S₂
Tree(S) is a root node containing the points in S with two subtrees as children which are recursively defined on S₁ and S₂

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

Let LMax(R(X)) denote size of the longest interval of the bounding hyperrectangle of point set X and let Left(X) / Right(X) denote its children. We give pseudocode for the FindPairs(A,B) function below.

FindPairs(A,B)
  if R(A) and R(B) are s-well-separated
    report pair(A,B)
  else
    if( LMax(R(A)) ≤ LMax(R(B)) )
      Recursively call FindPairs(A,Left(B)) and FindPairs(A,Right(B))
    else
      Recursively call FindPairs(Left(A),B) and FindPairs(Right(A),B)

Combining the s-well-separated pairs from all the calls of FindPairs(A,B) gives the WSPD for separation s.

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.^[1]
Solve the k-closest pairs problem in $O(n \lg n + k)$ time.^[1]
Solve the all-nearest neighbors problem in $O(n \lg n)$ time.^[1]
Provide a $(1-\epsilon)$ -approximation of the diameter of a point set in $O(n \lg n)$ time.^[1]
Directly induce a t-spanner of a point set.^[1]
Provide a t-approximation of the Euclidean minimum spanning tree in d dimensions in $O(n \lg n)$ time.

References

↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Smid, Michiel (16 August 2005). "The well-separated pair decomposition and its applications". Retrieved 26 March 2014.
↑ 2.0 2.1 Callahan, P. B. and Kosaraju, S. R. (January 1995). "A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields". Journal of the ACM 42 (1): 67–90. doi:10.1145/200836.200853.