Answers are grounded in this paper and cite their sources.
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/εᵈ) dumbbells in Rᵈ, but many point sets have far smaller WSPDs of both kinds. For d≥2, the known $O(1)$-approximations of the minimum size WSPD that preserve the separation $ε$ have unspecified factors, above 10⁷ for $d=2$ by our estimates. For cover WSPDs, we give an O(n²log n)-time sweep approximation algorithm with a factor 40 in the plane for ε≤1/16. It extends to Rᵈ with a factor 2O(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 ε≤1/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.
No takes yet. Share an insight, caveat, or question.
Guilherme Dias da Fonseca (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: