Certified Small Well-Separated Pair Decompositions in Practice

Given n points and $ε>0$, a well-separated pair decomposition (WSPD) is a collection of dumbbells {X,Y}, where X and Y have diameter at most $ε$ times their distance, such that every pair of points has one point in X and the other in Y for some dumbbell. A partition WSPD covers every pair exactly once, and a cover WSPD at least once. Callahan and Kosaraju give a partition WSPD with $O(n/ε^d)$ dumbbells in $R^d$, but many point sets have far smaller WSPDs of both kinds. For $d\ge2$, the known $O(1)$-approximations of the minimum size WSPD that preserve the separation $ε$ have unspecified factors, above $10^7$ for $d=2$ by our estimates. For cover WSPDs, we give an $O(n^2\log n)$-time sweep approximation algorithm with a factor 40 in the plane for $ε\le1/16$. It extends to $R^d$ with a factor $2^{O(d)}$. The sweep is also a lower-bound tool: its number of steps is a lower bound on the WSPD size. For partition WSPDs, we analyze quadtree and fair split tree constructions: in the plane and for $ε\le1/5$, they give constant approximation factors, the smallest of which is 252 for a randomly shifted and scaled quadtree. In experiments with $ε=1/20$, the number of sweep steps is at least 0.91 OPT for n = 500, where the optimum OPT is known, and a local search raises it to a lower bound of 0.99 OPT. A greedy variant of the sweep, which is still a certified 40-approximation, is at most 1.28 times the lower bound for n = 10000. Followed by a new local-search heuristic that shrinks the WSPD, it is within 0.02% of the optimum on every instance with n = 500, and at most 1.10 times the lower bound for n = 10000. We then show how to convert the cover WSPDs into partition WSPDs. For n = 10000, the conversion gives on average 1.13 times the lower bound, against 1.05 for the cover WSPD itself and 1.55 for the Callahan-Kosaraju partition WSPD.