Mohamad Farshi
The problem with the Well-Separated Pair Decomposition (WSPD) in some applications is that, even though the number of pairs in the WSPD is linear, the total number of points over all the pairs can be quadratic. In this talk we introduce a relaxed version of the WSPD, the Semi-Separated Pair Decomposition (SSPD) and present an algorithm which computes an SSPD which contains linear number of pairs and the total number of points over all the pairs is $O(n\log n)$. It is known that the total number of points over all pairs of such a decomposition has $\Omega(n\log n)$ lower bound.