$\newcommand{ \Re}{ \mathbb{ R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algorithms in low-dimensional Euclidean space and doubling metrics. This problem is computationally hard already $\Re^2$, and is also hard to approximate. We also introduce a new pair decomposition, removing the requirement that the diameters of the parts should be small. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size $O( \tfrac{ n}{ \varepsilon}\log n)$, which is dramatically smaller than the quadratic bound for WSPDs. In $\Re^d$, the bound improves to $O( d \tfrac{ n}{ \varepsilon}\log \tfrac{ 1}{ \varepsilon } )$.
Categories: cs.CG