A Bicriteria Approximation Scheme for the Minimum Well-Separated Pair Decomposition

A well-separated pair decomposition (WSPD) of a set $P$ of $n$ points covers all $\left(\genfrac{}{}{0px}{}{n}{2}\right)$ pairs of points by a family of dumbbells $\{X,Y\}$, each covering the pairs of $X\times Y$, such that the diameters of $X$ and $Y$ are at most an $\epsilon$-fraction of their distance. In ${\mathbb{R}}^d$, WSPDs with $O(n\mathrm{/}{\epsilon }^d)$ dumbbells always exist, but many inputs admit much smaller ones. However, computing a WSPD of minimum size is NP-hard in the plane. For $d\ge 2$, the only known approximation that preserves the separation has a factor of $2^{O(d)}$, and Buchin et al. (ESA 2026) asked whether a $(1+\delta )$-approximation exists. We give a bicriteria approximation scheme: for fixed $d$ and $\delta \in (0,1]$, we compute in $f(d,\delta )\cdot n^6$ time a $(1+\delta )\epsilon$-WSPD whose size is at most $(1+\delta )$ times the minimum size of an $\epsilon$-WSPD. The same holds in metric spaces of bounded doubling dimension. The algorithm combines shifting over scales with the local-growth technique of Nieberg, Hurink, and Kern, applied to a graph whose vertices are the pairs of points. In contrast, we show that in general metric spaces, relaxing the separation by a factor below $2$ keeps the problem hard: for every fixed rational $\epsilon \le 1\mathrm{/}4$, it is NP-hard to compute such a relaxed WSPD whose size is within a factor $n^c$ of the minimum, for every $c<2\mathrm{/}3$.