On Small Pair Decompositions for Point Sets

We study the problem of computing a minimum-size Well-Separated Pair Decomposition (WSPD) of a given point set. We obtain the following results for the minimum-size WSPD: (1) a constant-factor approximation in doubling metrics, (2) a simple 3-approximation in ℝ, and (3) an NP-hardness proof in ℝ². We also provide an optimal output-sensitive runtime for the algorithm in doubling metrics and an implementation of the 3-approximation algorithm in ℝ. Furthermore, we introduce a new pair-decomposition for point sets in a metric space. It is defined using a relaxed requirement that, for all pairs {X,Y} in the decomposition, all the distances of pairs of points in X × Y are equal up to a factor in [1 ± ε]. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size O(n/ε log n), which is dramatically smaller than the Θ(n²) bound for WSPDs. For a point set in ℝ^d, the bound improves to O(d n/ε log 1/ε).