Well-separated pair decomposition

File:Visual representation of well-separated pair.svg

Let $A,\; B$ be two disjoint sets of points in $\backslash 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 for each of $R(A)$ and $R(B)$ there exists a d-ball of radius $\backslash rho$ containing it, such that the two spheres have a minimum distance of at least $s\; \backslash rho$.{{cite journal | title=A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields |author1=Callahan, P. B. |author2=Kosaraju, S. R. |name-list-style=amp | journal=Journal of the ACM |date=January 1995 | volume=42 | issue=1 | pages=67–90 | doi=10.1145/200836.200853| doi-access=free }}

We consider a sequence of well-separated pairs of subsets of $S$, $(A\_1,\; B\_1),\; (A\_2,\; B\_2),\; \backslash ldots,\; (A\_m,B\_m)$ to be a well-separated pair decomposition (WSPD) of $S$ if for any two distinct points $p,\; q\; \backslash in\; S$, there exists precisely one $i$, $1\; \backslash leq\; i\; \backslash leq\; m$, such that either

• $p\; \backslash in\; A\_i$ and $q\; \backslash in\; B\_i$, or
• $q\; \backslash in\; A\_i$ and $p\; \backslash in\; B\_i$.

By way of constructing a fair split tree, it is possible to construct a WSPD of size $O(s^d\; n)$ in $O(n\; \backslash lg\; n)$ time.

The general principle of the split tree of a point set {{math|S}} is that each node {{math|u}} of the tree represents a set of points {{math|S_u}} and that the bounding box {{math|R(S_u)}} of {{math|S_u}} is split along its longest side in two equal parts which form the two children of {{math|u}} and their point set. It is done recursively until there is only one point in the set.

Let {{math|L_max(R(X))}} denote the size of the longest interval of the bounding hyperrectangle of point set {{math|X}} and let {{math|L_i(R(X))}} denote the size of the i-th dimension of the bounding hyperrectangle of point set {{math|X}}. We give pseudocode for the Split tree computation below.

{{math|SplitTree(S)}}

Let {{math|u}} be the node for {{math|S}}

if {{math|{{!}}S{{!}} {{=}} 1}}

{{math|R(u) :{{=}} R(S)}} // {{math|R(S)}} is a hyperrectangle which each side has a length of zero.

Store in {{math|u}} the only point in S.

else

Compute {{math|R(S)}}

Let the i-th dimension be the one where {{math|L_max(R(S)) {{=}} L_i(R(S))}}

Split {{math|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 {{math|S_v}} and {{math|S_w}}.

{{math|v :{{=}} SplitTree(S_v)}}

{{math|w :{{=}} SplitTree(S_w)}}

Store {{math|v}} and {{math|w}} as, respectively, the left and right children of {{math|u}}.

{{math|R(u) :{{=}} R(S)}}

return {{math|u}}

This algorithm runs in $O(n^2)$ time.

We give a more efficient algorithm that runs in $O(n\; \backslash lg\; n)$ time below. The goal is to loop over the list in only $O(n)$ operations per step of the recursion but only call the recursion on at most half the points each time.

Let {{math|S_i^j}} be the i-th coordinate of the j-th point in {{math|S}} such that {{math|S_i}} is sorted according to the i-th coordinate and {{math|p(S_i^j)}} be the point. Also, let {{math|h(R(S))}} be the hyperplane that splits the longest side of {{math|R(S)}} in two. Here is the algorithm in pseudo-code:

{{math|SplitTree(S, u)}}

if {{math|{{!}}S{{!}} {{=}} 1}}

{{math|R(u) :{{=}} R(S)}} // {{math|R(S)}} is a hyperrectangle which each side has a length of zero.

Store in {{math|u}} the only point in {{math|S}}.

else

{{math|size :{{=}} {{!}}S{{!}}}}

repeat

Compute {{math|R(S)}}

{{math|R(u) :{{=}} R(S)}}

{{math|j : {{=}} 1}}

{{math|k : {{=}} {{!}}S{{!}}}}

Let the i-th dimension be the one where {{math|L_max(R(S)) {{=}} L_i(R(S))}}

{{math|S_v : {{=}} ∅}}

{{math|S_w : {{=}} ∅}}

while {{math|S_i^j+1 < h(R(S))}} and {{math|S_i^k-1 > h(R(S))}}

{{math|size :{{=}} size - 1}}

{{math|S_v : {{=}} S_v ∪ {p(S_i^j)}}}

{{math|S_w : {{=}} S_w ∪ {p(S_i^k)}}}

{{math|j :{{=}} j + 1}}

{{math|k :{{=}} k - 1}}

Let {{math|v}} and {{math|w}} be respectively, the left and right children of {{math|u}}.

if {{math|S_i^j+1 > h(R(S))}}

{{math|S_w :{{=}} S \ S_v}}

{{math|u :{{=}} w}}

{{math|S :{{=}} S_w}}

{{math|SplitTree(S_v,v)}}

else if {{math|S_i^k-1 < h(R(S))}}

{{math|S_v :{{=}} S \ S_w}}

{{math|u :{{=}} v}}

{{math|S :{{=}} S_v}}

{{math|SplitTree(S_w,w)}}

until {{math|size ≤ {{frac|n|2}}}}

{{math|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.

File:Visual representation of a well-separated pair computed with the bounding boxes.svg

The WSPD can be extracted from such a split tree by calling the recursive {{math|FindPairs(v,w)}} function on the children of every node in the split tree. Let {{math|u_l}} / {{math|u_r}} denote the children of the node {{math|u}}. We give pseudocode for the {{math|FindWSPD(T, s)}} function below.

FindWSPD(T, s)

for each node u that is not a leaf in the split tree T do

FindPairs(u_l, u_r)

We give pseudocode for the {{math|FindPairs(v, w)}} function below.

FindPairs(v, w)

if {{math|S_v}} and {{math|S_w}} are well-separated with respect to {{math|s}}

report {{math|pair(S_v, S_w)}}

else

if( {{math|L_max(R(v)) ≤ L_max(R(w))}} )

Recursively call {{math|FindPairs(v, w_l)}} and {{math|FindPairs(v, w_r)}}

else

Recursively call {{math|FindPairs(v_l, w)}} and {{math|FindPairs(v_r, w)}}

Combining the {{math|s}}-well-separated pairs from all the calls of {{math|FindPairs(v,w)}} gives the WSPD for separation {{math|s}}.

{{collapse top|title=Proof of correctness of the algorithm}}

It is clear that the pairs returned by the algorithm are well-separated because of the return condition of the function {{math|FindPairs}}.

Now, we have to prove that for any distinct points $p$ and $q$ in $S$, there is a unique pair $\backslash \{A,\; B\backslash \}$ so that (i) $p\; \backslash in\; A$ and $q\; \backslash in\; B$ or (ii) $p\; \backslash in\; B$ and $q\; \backslash in\; A$. Assume without loss of generality that (i) holds.

Let $u$ be the lowest common ancestor of $p$ and $q$ in the split tree and let $v$ and $w$ be the children of $u$. Because of the last assumption, $p$ is in the subtree of $v$ and $q$ in the subtree of $w$. A call to {{math|FindPairs(v,w)}} is necessarily done in {{math|FindWSPD}}. 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 {{math|FindPairs}} leading to having $p$ in $A$ and $q$ in $B$.

Because $u$ is the lowest common ancestor of $p$ and $q$, calling {{math|FindPairs}} on the children of a higher node would result of $p$ and $q$ not being in a pair and calling {{math|FindPairs}} on the children in one of the nodes of one of the subtrees of $u$ would result by $p$ or $q$ not being in any pair. Thus, the pair $\backslash \{A,\; B\backslash \}$ is the unique one separating $p$ and $q$.

{{collapse bottom}}

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 $O(s^d\; n)$.

Lemma 1: Let $\backslash \{A,\; B\backslash \}$ be a well-separated pair with respect to $s$. Let $p,\; p\text{'}\; \backslash in\; A$ and $q\; \backslash in\; B$. Then, $|pp\text{'}|\; \backslash leq\; (2/s)|pq|$.

Proof: Because $p$ and $p\text{'}$ are in the same set, we have that $|pp\text{'}|\; \backslash leq\; 2\backslash rho$ where $\backslash rho$ is the radius of the enclosing circle of $A$ and $B$. Because $p$ and $q$ are in two well-separated sets, we have that $|pq|\; \backslash geq\; s\backslash rho$. We obtain that:

$\backslash begin\{align\}$

& \frac

pp'

{2} \leq \rho \leq \frac

pq

{s} \\

\Leftrightarrow & \\

& \frac

pp'

{2} \leq \frac

pq

{s} \\

\Leftrightarrow & \\

& |pp'| \leq \frac{2}{s}|pq| \\

\end{align}

Lemma 2: Let $\backslash \{A,\; B\backslash \}$ be a well-separated pair with respect to $s$. Let $p,\; p\text{'}\; \backslash in\; A$ and $q,\; q\text{'}\; \backslash in\; B$. Then, $|p\text{'}q\text{'}|\; \backslash leq\; (1+\; 4/s)|pq|$.

Proof: By the triangle inequality, we have:

$|p\text{'}q\text{'}|\; \backslash leq\; |p\text{'}p|\; +\; |pq|\; +\; |qq\text{'}|$

From Lemma 1, we obtain:

$\backslash begin\{align\}$

|p'q'| & \leq (2/s)|pq| + |pq| + (2/s)|pq| \\

& = (1+4/s)|pq|

\end{align}

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\; \backslash lg\; n)$ time.
• Solve the k-closest pairs problem in $O(n\; \backslash lg\; n\; +\; k)$ time.
• Solve the k-closest pair problem in $O(n\; \backslash lg\; n)$ time.{{cite journal|last1=Bespamyatnikh|first1=Sergei|last2=Segal|first2=Michael |title=Fast Algorithms for Approximating Distances.|journal=Algorithmica |volume=33 |issue=2 |pages=263–269|date=2002|doi=10.1007/s00453-001-0114-7|s2cid=9758120 }}
• Solve the all-nearest neighbors problem in $O(n\; \backslash lg\; n)$ time.
• Provide a $(1-\backslash epsilon)$-approximation of the diameter of a point set in $O(n\; \backslash lg\; n)$ time.
• Directly induce a t-spanner of a point set.
• Provide a t-approximation of the Euclidean minimum spanning tree in d dimensions in $O(n\; \backslash lg\; n)$ time.
• Provide a $(1+\backslash epsilon)$-approximation of the Euclidean minimum spanning tree in d dimensions in $O(n\; \backslash lg\; n\; +\; (\backslash epsilon^\{-2\}\; \backslash lg\; ^2\; \backslash frac\{1\}\{\backslash epsilon\})n)$ time.{{cite journal|last1=Arya|first1=Sunil|last2=Mount|first2=David M.|title=A fast and simple algorithm for computing approximate euclidean minimum spanning trees|journal=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms|date=2016|pages=1220–1233 |doi=10.1137/1.9781611974331.ch85 |isbn=978-1-61197-433-1 }}

{{reflist}}

Category:Computational geometry