On Small Pair Decompositions for Point Sets

Abstract

$\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(\frac{n}{\epsilon }\log n)$, which is dramatically smaller than the quadratic bound for WSPDs. In ${\Re }^d$, the bound improves to $O(d\frac{n}{\epsilon }\log \frac{1}{\epsilon })$.