betaFeedback

WorksComputer Science

Certified Small Well-Separated Pair Decompositions in Practice

Abstract

Given n points and ε>0ε>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)O(n/ε^d) dumbbells in RdR^d, but many point sets have far smaller WSPDs of both kinds. For d≥2d\ge2, the known O(1)O(1)-approximations of the minimum size WSPD that preserve the separation εε have unspecified factors, above 10710^7 for d=2d=2 by our estimates. For cover WSPDs, we give an O(n2log⁡n)O(n^2\log n)-time sweep approximation algorithm with a factor 40 in the plane for ε≤1/16ε\le1/16. It extends to RdR^d with a factor 2O(d)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 ε≤1/5ε\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ε=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.

2012 ACM Subject Classification Theory of computation →\to Computational geometry; Theory of computation →\to Approximation algorithms analysis

Keywords and phrases Well-separated pair decomposition, approximation algorithm, local search, set cover, algorithm engineering

Supplementary Material Software: https://github.com/gfonsecabr/small-wspd-experiments

Acknowledgements Use of AI: This paper was prepared with substantial help from the AI assistant Claude (Anthropic). It took part in developing the algorithms and proofs, writing the code and running the experiments, checking the references, and writing the text. The author checked all results and is responsible for the content.

Introduction

Let PP be a set of nn points in fixed dimension dd, and let ε∈(0,1)\varepsilon\in(0,1). We write ∥pq∥\lVert pq\rVert for the Euclidean distance between points pp and qq, diam⁡(X)\operatorname{diam}(X) for the diameter of a set X⊆PX \subseteq P, and dist⁡(X,Y)=min⁡x∈X,y∈Y∥xy∥\operatorname{dist}(X,Y)=\min_{x\in X,y\in Y}\lVert xy\rVert. A dumbbell {X,Y}\{X,Y\} consists of two disjoint nonempty sets X,Y⊆PX,Y \subseteq P, its sides, and it is ε\varepsilon-separated if max⁡{diam⁡(X),diam⁡(Y)}≤ε⋅dist⁡(X,Y)\max\{\operatorname{diam}(X),\operatorname{diam}(Y)\}\le\varepsilon\cdot\operatorname{dist}(X,Y).

An ε\varepsilon-WSPD of PP is a collection W\mathcal{W} of ε\varepsilon-separated dumbbells that together cover all (n2)\binom{n}{2} pairs of points, and ∣W∣|\mathcal{W}| is its size. A partition WSPD covers every pair exactly once, and we use the term cover WSPD to stress that pairs may be covered by multiple dumbbells.

WSPDs were introduced in [7] and are now a standard tool in computational geometry [17, 19]. The Callahan–Kosaraju (CK) construction [7] computes a partition ε\varepsilon-WSPD of size O(n/εd)O(n/\varepsilon^d) in O(nlog⁡n+n/εd)O(n\log n+n/\varepsilon^d) time, with dumbbells given as pairs of tree nodes. Several applications of WSPDs only use that every pair is covered at least once, so they work with cover WSPDs. Choosing one edge per dumbbell gives a tt-spanner with ∣W∣|W| edges [6, 17, 19], and hence an approximate minimum spanning tree [6, 19]; such sparse edge sets also speed up solvers for geometric tour problems [12]. The approximate diameter [19, 14] is found by inspecting every dumbbell once. Other applications, such as the computation of nn-body potential fields [7], approximate distance selection [3, 19], and the approximation of the sum of all pairwise distances [14], need a partition WSPD.

The bound O(n/εd)O(n/\varepsilon^d) is a worst-case bound, and many point sets have much smaller WSPDs. For example, the nn points pi=(i,(4/ε)i)p_i=(i,(4/\varepsilon)^i) have an ε\varepsilon-WSPD with only n−1n-1 dumbbells even in the partition version [5]. Since spanners and many other structures built from a WSPD inherit its size, a WSPD that is as small as possible is desirable.

The input of MINWSPD consists of PP and ε\varepsilon, and the goal is a cover ε\varepsilon-WSPD of PP of minimum size, which we denote by OPTε\mathrm{OPT}_{\varepsilon}, or by OPT\mathrm{OPT} if ε\varepsilon is clear from the context. A partition WSPD is in particular a cover WSPD. Therefore, every approximation factor with respect to OPTε\mathrm{OPT}_{\varepsilon} also holds with respect to the partition optimum.

Previous work. MINWSPD was introduced in [5]. It is NP-hard in the plane when ε\varepsilon may depend on nn, and in general metric spaces no polynomial-time algorithm achieves a factor ncn^c, for some constant c>0c>0, unless P = NP [5]. Table 1 lists the known approximation algorithms. For d≥2d\ge2, the only one stated for the separation ε\varepsilon is based on the net-tree WSPD [15], and its factor 2O(d)2^{O(d)} is unspecified; our rough estimate from its proof is 101110^{11} for d=2d=2. Greedy set cover over all maximal ε\varepsilon-separated dumbbells keeps the separation and gives an O(log⁡n)O(\log n)-approximation whenever their number is polynomial in nn, which holds on the line but is not known for d≥2d\ge2 [5]. The constant-factor algorithm of [16] works in every metric space but relaxes the separation (the constants 7 and 33 follow from its proof, see also [5]). In Rd\mathbb{R}^d, the relaxation can be undone: a grid cuts each side of a cεc\varepsilon-separated dumbbell into at most ⌈cd⌉d\lceil c\sqrt{d}\rceil^d pieces whose diameter is at most 1/c1/c times the larger diameter of the two sides, and the pieces form ε\varepsilon-separated dumbbells. For d=2d=2 and ε<1/33\varepsilon<1/33, the factor becomes 7⋅474≈3.4⋅1077\cdot47^4\approx3.4\cdot10^7. For d≥2d\ge2, the question of a (1+δ)(1+\delta)-approximation, or a simple O(1)O(1)-approximation, was raised in [5]. A bicriteria approximation scheme, which computes a (1+δ)ε(1+\delta)\varepsilon-WSPD of size at most (1+δ)OPTε(1+\delta)\mathrm{OPT}_{\varepsilon} in Rd\mathbb{R}^d and in doubling metrics, is given in [8], but its running time is doubly exponential in d/δd/\delta.

Our results. Table 1 places our algorithms among the known approximation results.

  1. Improved cover WSPD approximation factors (Theorem 3). For points in the plane and ε≤1/16\varepsilon\le1/16, a sweep algorithm computes a 40-approximation in O(n2log⁡n)O(n^2\log n) time and O(n2)O(n^2) space. It extends to Rd\mathbb{R}^d for every fixed dd (Theorem 11) with the same time and space bounds, with a factor 2048 for d=3d=3 and 2O(d)2^{O(d)} in general. It generalizes the 3-approximation of [5] for d=1d=1 and is a simple O(1)O(1)-approximation, as asked there.

  1. Improved partition WSPD approximation factors (Section 7). For points in the plane and ε≤1/5\varepsilon\le1/5, the CK construction on a fair split tree [7] outputs at most 1024 OPT dumbbells in O(nlog⁡n+OPT)O(n\log n+\mathrm{OPT}) time. The same size bound holds for the two variants of our experiments: CK boxCK\ box accepts two tree nodes if their bounding boxes are ε\varepsilon-separated, and CK exactCK\ exact, or just CKCK, if their point sets are. In the same time, the maximal separated pairs of same-level quadtree cells, with separation tested on the cells, form a partition ε\varepsilon-WSPD of size at most 529 OPT, and of expected size at most 252 OPT for a randomly shifted and scaled quadtree. The deterministic bounds extend to Rd\mathbb{R}^d.

  1. Small cover WSPD in practice (Section 5). A greedy variant of the sweep keeps the

approximation factor 40 and runs in O(n3)O(n^3) time (Theorem 7). The number of steps of the sweep is a lower bound on OPT. A local search on the anchors of the steps enlarges it to a lower bound LB (§ 3.3), which certifies the quality of any WSPD. For ε=1/20\varepsilon= 1/20 and n=500n = 500, where OPT is known, the greedy sweep is on average 1.03 OPT, against 1.17 OPT for the CK WSPD, and the lower bound is at least 0.99 OPT. For n=10000n = 10000, where OPT is out of reach, the greedy sweep and the CK WSPD are on average 1.22 LB and 1.55 LB. We present a local-search heuristic (§ 3.2) that post-processes any given WSPD with a single move, reshape, never increasing its size. For n=500n = 500, it brings the sweep to within 0.02% of OPT, and it reaches OPT on 13 of the 22 instances. For n=10000n = 10000, the sweep followed by local search is at most 1.10 LB and on average 1.05 LB.

4. Small partition WSPD in practice (§ 5). Converting the cover WSPD of the sweep followed by local search into a partition WSPD gives on average 1.006 OPT for n=500n = 500 and 1.13 LB for n=10000n = 10000, against 1.17 OPT and 1.55 LB for CK.

SettingProblemSizeSeparationTimeReference
R1\mathbb{R}^{1}cover(1+δ) OPTε(1+\delta)\,\mathrm{OPT}_{\varepsilon}ε\varepsilonnO(1/δ2)n^{O(1/\delta^2)}[5]
R1\mathbb{R}^{1}cover3 OPTε3\,\mathrm{OPT}_{\varepsilon}ε\varepsilonO(nlog⁡n)O(n\log n)[5]
R1\mathbb{R}^{1}both10 OPTε10\,\mathrm{OPT}_{\varepsilon}ε\varepsilonpolynomial[5]
Rd\mathbb{R}^{d}both2O(d)OPTε2^{O(d)}\mathrm{OPT}_{\varepsilon}ε\varepsilon2O(d)(nlog⁡n+OPT)∗2^{O(d)}(n\log n+\mathrm{OPT})^*[5, 15]
Rd\mathbb{R}^{d}cover(1+δ) OPTε(1+\delta)\,\mathrm{OPT}_{\varepsilon}(1+δ)ε(1+\delta)\varepsilonf(d,δ)n6f(d,\delta)n^6[8]
Any metriccover7 OPTε7\,\mathrm{OPT}_{\varepsilon}33ε33\varepsilonpolynomial[16]
R2\mathbb{R}^{2}, ε≤1/16\varepsilon\le1/16cover40 OPTε40\,\mathrm{OPT}_{\varepsilon}ε\varepsilonO(n2log⁡n)O(n^2\log n)Theorem 3
R2\mathbb{R}^{2}, ε≤1/5\varepsilon\le1/5both1024 OPTε1024\,\mathrm{OPT}_{\varepsilon}ε\varepsilonO(nlog⁡n+OPT)O(n\log n+\mathrm{OPT})[7], § 7
R2\mathbb{R}^{2}, ε≤1/5\varepsilon\le1/5both529 OPTε529\,\mathrm{OPT}_{\varepsilon}ε\varepsilonO(nlog⁡n+OPT)O(n\log n+\mathrm{OPT})§ 7
R2\mathbb{R}^{2}, ε≤1/5\varepsilon\le1/5both252 OPTε∗252\,\mathrm{OPT}_{\varepsilon}^{*}ε\varepsilonO(nlog⁡n+OPT)O(n\log n+\mathrm{OPT})§ 7
Rd\mathbb{R}^{d}, ε≤1/16\varepsilon\le1/16cover2O(d)OPTε2^{O(d)}\mathrm{OPT}_{\varepsilon}ε\varepsilonO(n2log⁡n)O(n^2\log n)Theorem 11

Table 1. Approximation algorithms for MINWSPD\mathrm{MINWSPD}. Both: outputs a partition WSPD. ∗^*: expected.

Section 2 presents the sweep and its analysis, Section 3 a greedy variant of the sweep and the local search for smaller WSPDs and larger lower bounds, and Section 4 the extension of the sweep to higher dimensions. Section 5 reports the experiments, in the plane and, in § 5.3, in R3\mathbb{R}^3. Section 6 extends the sweep to larger ε\varepsilon. The partition WSPD constructions are analyzed in § 7.

Sweep Algorithm

This section presents the sweep 40-approximation algorithm for points in the plane. Let ≺\prec denote the lexicographic order on R2\mathbb{R}^2 (by first coordinate, then by second coordinate), and write p⪯qp \preceq q if p≺qp \prec q or p=qp = q. We write B(c,r)B(c,r) for the closed disk of radius rr centered at cc.

References

  1. [1]Diogo V. Andrade, Mauricio G. C. Resende, and Renato F. Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525–547, 2012. doi:10.1007/s10732-012-9164-4.
  2. [2]Sanjeev Arya, Prolay P. Pal, and ... Fast polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753–782, 1998. doi:10.1145/290179.290180.
  3. [3]Sergei Bespamyatnikh and Michael Segal. Fast algorithms for approximating distances. Algorithmica, 33(2):263–269, 2002. doi:10.1007/s00453-001-0114-7.DOI
  4. [4]Coen Bron and Joep Kerbosch. Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9):575–577, 1973. doi:10.1145/362342.362367.DOI
  5. [5]Kevin Buchin, Jacobus Conradi, Sariel Har-Peled, Antonia Kalb, Abhiruk Lahiri, Lukas Plätz, Carolin Rehs, and Sampson Wong. On small pair decompositions for point sets. In Proc. 34th Annual European Symposium on Algorithms (ESA), volume 388 of LIPICs, pages 102:1–102:22, 2026. Full version: arXiv:2601.22728. doi:10.4230/LIPIcs.ESA.2026.102.DOI
  6. [6]Paul B. Callahan and S. Rao Kosaraju. Fast algorithms for some geometric graph problems in higher dimensions. In Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 291–300, 1993.DOI
  7. [7]Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67–90, 1995. doi:10.1145/200836.200853.DOI
  8. [8]Guilherme D. da Fonseca. A bicriteria approximation scheme for the minimum well-separated pair decomposition, 2026. arXiv:2610.13650. doi:10.48550/arXiv.2610.13650.DOI
  9. [9]9 Guilherme D. da Fonseca. Pangolin: Plane geometry library. https://github.com/gfonsecabr/pgl, 2026.
  10. [10]10 Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Area-optimal simple polygonalizations: The CG challenge 2019. ACM Journal of Experimental Algorithmics, 27:2.4:1–2.4:12, 2022. doi:10.1145/3504000.DOI
  11. [11]11 Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004. doi:10.1016/j.jcss.2004.04.011.
  12. [12]12 Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Eike Niehs. Edge sparsification for geometric tour problems. Comput. Geom. Topol., 3(1):1:1–1:23, 2024. doi:10.57717/cgt.v3i1.20.
  13. [13]13 Andrea Grosso, Marco Locatelli, and Wayne Pullan. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics, 14(6):587–612, 2008. doi:10.1007/s10732-007-9055-x.DOI
  14. [14]14 Sariel Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. American Mathematical Society, 2011. doi:10.1090/surv/173.
  15. [15]15 Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput., 35(5):1148–1184, 2006. doi:10.1137/S009753970446281.
  16. [16]16 Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. Well-separated pairs decomposition revisited, 2025. arXiv:2509.05997.
  17. [17]17 Giri Narasimhan and Michiel H. M. Smid. Geometric Spanner Networks. Cambridge University Press, 2007. doi:10.1017/CBO9780511546884.DOI
  18. [18]18 Wayne Pullan and Holger H. Hoos. Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research, 25:159–185, 2006. doi:10.1613/jair.1815.DOI
  19. [19]19 Michiel H. M. Smid. The well-separated pair decomposition and its applications. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, Volume 2: Contemporary and Emerging Applications, chapter 4, pages 71–84. Chapman and Hall/CRC, 2nd edition, 2018. doi:10.1201/9781351235429.
  20. [20]20 Stanford Computer Graphics Laboratory. The Stanford 3D scanning repository. http://graphics.stanford.edu/data/3Dscanrep/. Meshes used: https://github.com/alecjacobson/common-3d-test-models.

Paper details

vlnc:W_3xukbd35
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents