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 P P P be a set of n n n points in fixed dimension d d d , and let ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . We write ∥ p q ∥ \lVert pq\rVert ∥ pq ∥ for the Euclidean distance between points p p p and q q q , diam ( X ) \operatorname{diam}(X) diam ( X ) for the diameter of a set X ⊆ P X \subseteq P X ⊆ P , and dist ( X , Y ) = min x ∈ X , y ∈ Y ∥ x y ∥ \operatorname{dist}(X,Y)=\min_{x\in X,y\in Y}\lVert xy\rVert dist ( X , Y ) = min x ∈ X , y ∈ Y ∥ x y ∥ . A dumbbell { X , Y } \{X,Y\} { X , Y } consists of two disjoint nonempty sets X , Y ⊆ P X,Y \subseteq P X , Y ⊆ 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) max { diam ( X ) , diam ( Y )} ≤ ε ⋅ dist ( X , Y ) .
An ε \varepsilon ε -WSPD of P P P is a collection W \mathcal{W} W of ε \varepsilon ε -separated dumbbells that together cover all ( n 2 ) \binom{n}{2} ( 2 n ) pairs of points, and ∣ W ∣ |\mathcal{W}| ∣ 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) O ( n / ε d ) in O ( n log n + n / ε d ) O(n\log n+n/\varepsilon^d) O ( n log n + n / ε 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 t t t -spanner with ∣ W ∣ |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 n n n -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) O ( n / ε d ) is a worst-case bound, and many point sets have much smaller WSPDs. For example, the n n n points p i = ( i , ( 4 / ε ) i ) p_i=(i,(4/\varepsilon)^i) p i = ( i , ( 4/ ε ) i ) have an ε \varepsilon ε -WSPD with only n − 1 n-1 n − 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 P P P and ε \varepsilon ε , and the goal is a cover ε \varepsilon ε -WSPD of P P P of minimum size, which we denote by O P T ε \mathrm{OPT}_{\varepsilon} OPT ε , or by O P T \mathrm{OPT} OPT if ε \varepsilon ε is clear from the context. A partition WSPD is in particular a cover WSPD. Therefore, every approximation factor with respect to O P T ε \mathrm{OPT}_{\varepsilon} OPT ε 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 n n n , and in general metric spaces no polynomial-time algorithm achieves a factor n c n^c n c , for some constant c > 0 c>0 c > 0 , unless P = NP [5 ] . Table 1 lists the known approximation algorithms. For d ≥ 2 d\ge2 d ≥ 2 , the only one stated for the separation ε \varepsilon ε is based on the net-tree WSPD [15 ] , and its factor 2 O ( d ) 2^{O(d)} 2 O ( d ) is unspecified; our rough estimate from its proof is 10 11 10^{11} 1 0 11 for d = 2 d=2 d = 2 . Greedy set cover over all maximal ε \varepsilon ε -separated dumbbells keeps the separation and gives an O ( log n ) O(\log n) O ( log n ) -approximation whenever their number is polynomial in n n n , which holds on the line but is not known for d ≥ 2 d\ge2 d ≥ 2 [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 R d \mathbb{R}^d R d , the relaxation can be undone: a grid cuts each side of a c ε c\varepsilon c ε -separated dumbbell into at most ⌈ c d ⌉ d \lceil c\sqrt{d}\rceil^d ⌈ c d ⌉ d pieces whose diameter is at most 1 / c 1/c 1/ c times the larger diameter of the two sides, and the pieces form ε \varepsilon ε -separated dumbbells. For d = 2 d=2 d = 2 and ε < 1 / 33 \varepsilon<1/33 ε < 1/33 , the factor becomes 7 ⋅ 47 4 ≈ 3.4 ⋅ 10 7 7\cdot47^4\approx3.4\cdot10^7 7 ⋅ 4 7 4 ≈ 3.4 ⋅ 1 0 7 . For d ≥ 2 d\ge2 d ≥ 2 , the question of a ( 1 + δ ) (1+\delta) ( 1 + δ ) -approximation, or a simple O ( 1 ) O(1) O ( 1 ) -approximation, was raised in [5 ] . A bicriteria approximation scheme, which computes a ( 1 + δ ) ε (1+\delta)\varepsilon ( 1 + δ ) ε -WSPD of size at most ( 1 + δ ) O P T ε (1+\delta)\mathrm{OPT}_{\varepsilon} ( 1 + δ ) OPT ε in R d \mathbb{R}^d R d and in doubling metrics, is given in [8 ] , but its running time is doubly exponential in d / δ d/\delta d / δ .
Our results. Table 1 places our algorithms among the known approximation results.
Improved cover WSPD approximation factors (Theorem 3). For points in the plane and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , a sweep algorithm computes a 40-approximation in O ( n 2 log n ) O(n^2\log n) O ( n 2 log n ) time and O ( n 2 ) O(n^2) O ( n 2 ) space. It extends to R d \mathbb{R}^d R d for every fixed d d d (Theorem 11) with the same time and space bounds, with a factor 2048 for d = 3 d=3 d = 3 and 2 O ( d ) 2^{O(d)} 2 O ( d ) in general. It generalizes the 3-approximation of [5 ] for d = 1 d=1 d = 1 and is a simple O ( 1 ) O(1) O ( 1 ) -approximation, as asked there.
Improved partition WSPD approximation factors (Section 7). For points in the plane and ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 , the CK construction on a fair split tree [7 ] outputs at most 1024 OPT dumbbells in O ( n log n + O P T ) O(n\log n+\mathrm{OPT}) O ( n log n + OPT ) time. The same size bound holds for the two variants of our experiments: C K b o x CK\ box C K b o x accepts two tree nodes if their bounding boxes are ε \varepsilon ε -separated, and C K e x a c t CK\ exact C K e x a c t , or just C K CK C K , 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 R d \mathbb{R}^d R d .
Small cover WSPD in practice (Section 5). A greedy variant of the sweep keeps the
approximation factor 40 and runs in O ( n 3 ) O(n^3) 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 ε = 1/20 and n = 500 n = 500 n = 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 = 10000 n = 10000 n = 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 = 500 n = 500 n = 500 , it brings the sweep to within 0.02% of OPT, and it reaches OPT on 13 of the 22 instances. For n = 10000 n = 10000 n = 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 = 500 n = 500 n = 500 and 1.13 LB for n = 10000 n = 10000 n = 10000 , against 1.17 OPT and 1.55 LB for CK.
Table 1. Approximation algorithms for M I N W S P D \mathrm{MINWSPD} 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 R 3 \mathbb{R}^3 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 R 2 \mathbb{R}^2 R 2 (by first coordinate, then by second coordinate), and write p ⪯ q p \preceq q p ⪯ q if p ≺ q p \prec q p ≺ q or p = q p = q p = q . We write B ( c , r ) B(c,r) B ( c , r ) for the closed disk of radius r r r centered at c c c .
Pieces. For a disk B B B of radius ρ \rho ρ , we use a fixed partition of B B B into 8 pieces: the concentric disk of radius 0.434 ρ 0.434\rho 0.434 ρ , and the 7 sectors of angle 2 π / 7 2\pi/7 2 π /7 of the annulus between radii 0.434 ρ 0.434\rho 0.434 ρ and ρ \rho ρ . For the half-disk B + B^+ B + , which consists of the points of B B B whose first coordinate is at least that of its center, we use 5 pieces: the concentric half-disk of radius 0.4 ρ 0.4\rho 0.4 ρ , and the 4 sectors of angle π / 4 \pi/4 π /4 of the half-annulus between radii 0.4 ρ 0.4\rho 0.4 ρ and ρ \rho ρ . Points on the boundary between two pieces are assigned to one of them arbitrarily, so the pieces partition the disk and the half-disk. The inner radii are chosen so that all pieces have roughly the same diameter.
Lemma 1. Every piece of the disk partition has diameter at most 0.868 ρ 0.868\rho 0.868 ρ , and every piece of the half-disk partition has diameter at most 0.8 ρ 0.8\rho 0.8 ρ .
Proof. Assume ρ = 1 \rho= 1 ρ = 1 . The diameter of a set is attained by two extreme points of its convex hull. For an annular sector with angle less than π \pi π , these are the two inner corners and the points of the outer arc. Two points of the outer arc are at distance at most 2 sin ( φ / 2 ) 2\sin(\varphi/2) 2 sin ( φ /2 ) , and the distance from an inner corner to a point of the outer arc increases with the angle between them. Hence an annular sector with inner radius a < 1 a < 1 a < 1 , outer radius 1 1 1 , and angle φ ≤ π / 2 \varphi\le\pi/2 φ ≤ π /2 has diameter max { 2 sin ( φ / 2 ) , 1 + a 2 − 2 a cos φ , 1 − a } \max\{2\sin(\varphi/2),\sqrt{1+a^2-2a\cos\varphi},1-a\} max { 2 sin ( φ /2 ) , 1 + a 2 − 2 a cos φ , 1 − a } . For φ = 2 π / 7 \varphi= 2\pi/7 φ = 2 π /7 and a = 0.434 a = 0.434 a = 0.434 , these values are 0.8678 0.8678 0.8678 , 0.804 0.804 0.804 , and 0.566 0.566 0.566 . For φ = π / 4 \varphi= \pi/4 φ = π /4 and a = 0.4 a = 0.4 a = 0.4 , they are 0.765 0.765 0.765 , 0.771 0.771 0.771 , and 0.6 0.6 0.6 . The central pieces have diameters 0.868 0.868 0.868 and 0.8 0.8 0.8 .
Algorithm. Initially, no pair is covered. The algorithm processes the points p ∈ P p \in P p ∈ P in the order ≺ \prec ≺ , and for each such p p p the points q ≻ p q \succ p q ≻ p in arbitrary order. If the pair { p , q } \{p,q\} { p , q } is not yet covered, the algorithm performs a step with anchor { p , q } \{p,q\} { p , q } , as follows. Let D = ∥ p q ∥ D = \lVert pq\rVert D = ∥ pq ∥ . Let A 1 , … , A 5 A_1,\ldots,A_5 A 1 , … , A 5 be the intersections of { z ∈ P : z ⪰ p } \{z \in P : z \succeq p\} { z ∈ P : z ⪰ p } with the pieces of the half-disk B + ( p , ε D ) \mathbb{B}^{+}(p,\varepsilon D) B + ( p , ε D ) , and let C 1 , … , C 8 C_1,\ldots,C_8 C 1 , … , C 8 be the intersections of P P P with the pieces of the disk B ( q , ε D ) \mathbb{B}(q,\varepsilon D) B ( q , ε D ) . The step outputs every dumbbell { A i , C k } \{A_i,C_k\} { A i , C k } whose sides are both nonempty (Figure 1 ), at most 5 ⋅ 8 = 40 5\cdot8 = 40 5 ⋅ 8 = 40 dumbbells. We call these dumbbells the fixed collection of the step.
Figure 1. A step of the sweep with anchor { p , q } \{p,q\} { p , q } . The step outputs a dumbbell { A i , C k } \{A_i,C_k\} { A i , C k } , such as the one highlighted, for every two nonempty pieces.
Observation 2 (Locality). If an ε \varepsilon ε -separated dumbbell { X , Y } \{X,Y\} { X , Y } covers { x , y } \{x,y\} { x , y } and ℓ = dist ( X , Y ) \ell= \operatorname{dist}(X,Y) ℓ = dist ( X , Y ) , then ℓ ≤ ∥ x y ∥ ≤ ( 1 + 2 ε ) ℓ \ell\le\lVert xy\rVert\le(1+2\varepsilon)\ell ℓ ≤ ∥ x y ∥ ≤ ( 1 + 2 ε ) ℓ , and each side lies in the disk of radius ε ℓ \varepsilon\ell ε ℓ centered at any of its points.
Theorem 3. For P ⊂ R 2 P \subset\mathbb{R}^2 P ⊂ R 2 and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , the sweep performs at most OPT ε \operatorname{OPT}_{\varepsilon} OPT ε steps and outputs an ε \varepsilon ε -WSPD of size at most 40 OPT ε 40\operatorname{OPT}_{\varepsilon} 40 OPT ε in O ( n 2 log n ) O(n^2\log n) O ( n 2 log n ) time and O ( n 2 ) O(n^2) O ( n 2 ) space.
Proof. Validity. The disks B ( p , ε D ) \mathbb{B}(p,\varepsilon D) B ( p , ε D ) and B ( q , ε D ) \mathbb{B}(q,\varepsilon D) B ( q , ε D ) are disjoint since ε < 1 / 2 \varepsilon< 1/2 ε < 1/2 . By Lemma 1, diam ( A i ) , diam ( C k ) ≤ 0.868 ε D \operatorname{diam}(A_i),\operatorname{diam}(C_k) \le0.868\varepsilon D diam ( A i ) , diam ( C k ) ≤ 0.868 ε D , while dist ( A i , C k ) ≥ ( 1 − 2 ε ) D \operatorname{dist}(A_i,C_k) \ge(1-2\varepsilon)D dist ( A i , C k ) ≥ ( 1 − 2 ε ) D . Since 0.868 ≤ 1 − 2 ε 0.868 \le1-2\varepsilon 0.868 ≤ 1 − 2 ε for ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , every output dumbbell is ε \varepsilon ε -separated. Every pair { p , q } \{p,q\} { p , q } with p ≺ q p \prec q p ≺ q is covered once p p p is processed, since the step with anchor { p , q } \{p,q\} { p , q } covers it (p p p lies in some A i A_i A i , q q q in some C k C_k C k ).
Invariant. By the validity argument and the processing order, when the step with anchor { p , q } \{p,q\} { p , q } starts, every pair { x , y } \{x,y\} { x , y } with min ≺ { x , y } ≺ p \min_{\prec}\{x,y\} \prec p min ≺ { x , y } ≺ p is already covered. Charging. Fix a minimum ε \varepsilon ε -WSPD W ∗ \mathcal{W}^* W ∗ . Charge the step with anchor { p , q } \{p,q\} { p , q } to some Z = { X , Y } ∈ W ∗ Z=\{X,Y\}\in\mathcal{W}^* Z = { X , Y } ∈ W ∗ covering { p , q } \{p,q\} { p , q } , with p ∈ X p\in X p ∈ X and q ∈ Y q\in Y q ∈ Y . Let ℓ = dist ( X , Y ) ≤ D \ell=\operatorname{dist}(X,Y)\le D ℓ = dist ( X , Y ) ≤ D . By Observation 2, X ⊆ B ( p , ε ℓ ) ⊆ B ( p , ε D ) X\subseteq B(p,\varepsilon\ell)\subseteq B(p,\varepsilon D) X ⊆ B ( p , ε ℓ ) ⊆ B ( p , ε D ) and Y ⊆ B ( q , ε D ) Y\subseteq B(q,\varepsilon D) Y ⊆ B ( q , ε D ) .
Let { x , y } \{x,y\} { x , y } , with x ∈ X x\in X x ∈ X and y ∈ Y y\in Y y ∈ Y , be a pair that is not covered before the step. By the invariant, x ⪰ p x\succeq p x ⪰ p , so x ∈ B + ( p , ε D ) x\in B^+(p,\varepsilon D) x ∈ B + ( p , ε D ) lies in some A i A_i A i , and y y y lies in some C k C_k C k . Hence, after the step, every pair covered by Z Z Z is covered. In particular, no later anchor is covered by Z Z Z , and Z Z Z is charged only once. Hence distinct steps are charged to distinct dumbbells of W ∗ \mathcal{W}^* W ∗ , and there are at most ∣ W ∗ ∣ |\mathcal{W}^*| ∣ W ∗ ∣ steps. Since each step outputs at most 5 ⋅ 8 = 40 5\cdot8=40 5 ⋅ 8 = 40 dumbbells, the output has size at most 40 ∣ W ∗ ∣ 40|\mathcal{W}^*| 40∣ W ∗ ∣ . The running time is analyzed below.
The condition ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 keeps constants simple. With inner radius sin ( π / 7 ) ρ \sin(\pi/7)\rho sin ( π /7 ) ρ instead of 0.434 ρ 0.434\rho 0.434 ρ , every disk piece has diameter at most 2 sin ( π / 7 ) ρ 2\sin(\pi/7)\rho 2 sin ( π /7 ) ρ , and the factor 40 only needs ε ≤ 1 / 2 − sin ( π / 7 ) ≈ 1 / 15.12 \varepsilon\le1/2-\sin(\pi/7)\approx1/15.12 ε ≤ 1/2 − sin ( π /7 ) ≈ 1/15.12 . For larger ε \varepsilon ε , more pieces give larger factors (Section 6).
Two pairs are compatible if a single ε \varepsilon ε -separated dumbbell covers both of them.
Observation 4 (Heredity). If { X , Y } \{X,Y\} { X , Y } is ε \varepsilon ε -separated, then so is { X ′ , Y ′ } \{X',Y'\} { X ′ , Y ′ } for all nonempty X ′ ⊆ X X'\subseteq X X ′ ⊆ X and Y ′ ⊆ Y Y'\subseteq Y Y ′ ⊆ Y . Hence { a , a ′ } \{a,a'\} { a , a ′ } and { b , b ′ } \{b,b'\} { b , b ′ } are compatible if and only if { { a , b } , { a ′ , b ′ } } \{\{a,b\},\{a',b'\}\} {{ a , b } , { a ′ , b ′ }} or { { a , b ′ } , { a ′ , b } } \{\{a,b'\},\{a',b\}\} {{ a , b ′ } , { a ′ , b }} has disjoint sides and is ε \varepsilon ε -separated.
For the step with anchor { p , q } \{p,q\} { p , q } , let R p q R_{pq} R pq be the set of pairs { x , y } \{x,y\} { x , y } that are uncovered when the step starts, are compatible with { p , q } \{p,q\} { p , q } , and satisfy x , y ⪰ p x,y\succeq p x , y ⪰ p .
Observation 5. If every step of the sweep, with anchor { p , q } \{p,q\} { p , q } , covers R p q R_{pq} R pq , then the anchors are pairwise incompatible, so the number of steps is at most OPT ε \operatorname{OPT}_{\varepsilon} OPT ε .
Proof. Let { p ′ , q ′ } \{p',q'\} { p ′ , q ′ } be the anchor of a step performed after the step with anchor { p , q } \{p,q\} { p , q } . Both p ′ p' p ′ and q ′ q' q ′ are ⪰ p \succeq p ⪰ p , and { p ′ , q ′ } \{p',q'\} { p ′ , q ′ } was uncovered when the step with anchor { p , q } \{p,q\} { p , q } was performed. If the two anchors were compatible, that step would have covered { p ′ , q ′ } \{p',q'\} { p ′ , q ′ } , a contradiction. Since no ε \varepsilon ε -separated dumbbell covers two anchors, every ε \varepsilon ε -WSPD has at least as many dumbbells as there are steps.
The fixed collection covers R p q R_{pq} R pq for every ε < 1 / 2 \varepsilon<1/2 ε < 1/2 (the condition ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 is needed only for its dumbbells to be ε \varepsilon ε -separated). Indeed, the charging argument uses only that Z Z Z is an ε \varepsilon ε -separated dumbbell that covers { p , q } \{p,q\} { p , q } , and if { x , y } \{x,y\} { x , y } is compatible with { p , q } \{p,q\} { p , q } , then, by Observation 4, { { p , x } , { q , y } } \{\{p,x\},\{q,y\}\} {{ p , x } , { q , y }} or { { p , y } , { q , x } } \{\{p,y\},\{q,x\}\} {{ p , y } , { q , x }} is such a dumbbell.
Lemma 6. Let ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 . Every pair is covered by the output dumbbells of at most 360 steps of the sweep, and by at most one output dumbbell of each step.
Proof. At most one dumbbell per step. Let { x , y } \{x,y\} { x , y } be covered in the step with anchor { p , q } \{p,q\} { p , q } , and let D = ∥ p q ∥ D=\lVert pq\rVert D = ∥ pq ∥ . The disks B ( p , ε D ) B(p,\varepsilon D) B ( p , ε D ) and B ( q , ε D ) B(q,\varepsilon D) B ( q , ε D ) are disjoint, so one endpoint, say x x x , lies in B ( p , ε D ) B(p,\varepsilon D) B ( p , ε D ) and the other in B ( q , ε D ) B(q,\varepsilon D) B ( q , ε D ) . The pieces partition each disk, so exactly one output dumbbell of the step covers { x , y } \{x,y\} { x , y } .
At most 360 steps. Let L = ∥ x y ∥ L=\lVert xy\rVert L = ∥ x y ∥ . We split the steps whose output covers { x , y } \{x,y\} { x , y } into two classes, according to whether x x x lies in the disk around the first or the second point of the anchor, and we bound the size of each class by 180. Consider the class of steps with anchors { p j , q j } \{p_j,q_j\} { p j , q j } such that x ∈ B ( p j , ε D j ) x\in B(p_j,\varepsilon D_j) x ∈ B ( p j , ε D j ) and y ∈ B ( q j , ε D j ) y\in B(q_j,\varepsilon D_j) y ∈ B ( q j , ε D j ) , where D j = ∥ p j q j ∥ D_j=\lVert p_jq_j\rVert D j = ∥ p j q j ∥ . By the triangle inequality, ( 1 − 2 ε ) D j ≤ L ≤ ( 1 + 2 ε ) D j (1-2\varepsilon)D_j\le L\le(1+2\varepsilon)D_j ( 1 − 2 ε ) D j ≤ L ≤ ( 1 + 2 ε ) D j . Therefore, all p j p_j p j lie in B ( x , r ) B(x,r) B ( x , r ) and all q j q_j q j lie in B ( y , r ) B(y,r) B ( y , r ) , where r = ε L / ( 1 − 2 ε ) r=\varepsilon L/(1-2\varepsilon) r = ε L / ( 1 − 2 ε ) . Since 2 r < L 2r<L 2 r < L for ε < 1 / 4 \varepsilon<1/4 ε < 1/4 , these two disks are disjoint, so the sets { p j , p k } \{p_j,p_k\} { p j , p k } and { q j , q k } \{q_j,q_k\} { q j , q k } below are disjoint. For j ≠ k j\ne k j = k , the anchors are incompatible by Observation 5, so the dumbbell { { p j , p k } , { q j , q k } } \{\{p_j, p_k\}, \{q_j, q_k\}\} {{ p j , p k } , { q j , q k }} is not ε \varepsilon ε -separated. Since its distance is at least L − 2 r L - 2r L − 2 r ,
max { ∥ p j p k ∥ , ∥ q j q k ∥ } > s , where s = ε ( L − 2 r ) = r ( 1 − 4 ε ) ≥ 3 r / 4. \max\{\lVert p_jp_k\rVert, \lVert q_jq_k\rVert\} > s, \qquad\text{where } s = \varepsilon(L - 2r) = r(1 - 4\varepsilon) \geq3r/4. max {∥ p j p k ∥ , ∥ q j q k ∥} > s , where s = ε ( L − 2 r ) = r ( 1 − 4 ε ) ≥ 3 r /4.
For j ≠ k j \ne k j = k , if the products B ( p j , s / 2 ) × B ( q j , s / 2 ) \mathbb{B}(p_j, s/2) \times\mathbb{B}(q_j, s/2) B ( p j , s /2 ) × B ( q j , s /2 ) and B ( p k , s / 2 ) × B ( q k , s / 2 ) \mathbb{B}(p_k, s/2) \times\mathbb{B}(q_k, s/2) B ( p k , s /2 ) × B ( q k , s /2 ) of disks shared a point ( u , v ) (u,v) ( u , v ) , then ∥ p j p k ∥ ≤ ∥ p j u ∥ + ∥ u p k ∥ ≤ s \lVert p_jp_k\rVert\leq\lVert p_ju\rVert+ \lVert up_k\rVert\leq s ∥ p j p k ∥ ≤ ∥ p j u ∥ + ∥ u p k ∥ ≤ s and, similarly, ∥ q j q k ∥ ≤ s \lVert q_jq_k\rVert\leq s ∥ q j q k ∥ ≤ s . Hence these products are pairwise disjoint. They are contained in B ( x , r + s / 2 ) × B ( y , r + s / 2 ) \mathbb{B}(x,r+s/2) \times\mathbb{B}(y,r+s/2) B ( x , r + s /2 ) × B ( y , r + s /2 ) . The measure of a product of two disks is the product of their areas, so comparing areas, the class has at most ( ( r + s / 2 ) / ( s / 2 ) ) 4 = ( 1 + 2 r / s ) 4 ≤ ( 11 / 3 ) 4 < 181 ((r+s/2)/(s/2))^4 = (1+2r/s)^4 \leq(11/3)^4 < 181 (( r + s /2 ) / ( s /2 ) ) 4 = ( 1 + 2 r / s ) 4 ≤ ( 11/3 ) 4 < 181 steps.
Proof of the running time in Theorem 3. We store the covered pairs in an n × n n \times n n × n table. For every point c ∈ P c \in P c ∈ P , we also store the list of the points of P P P sorted by distance from c c c . These lists take O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) time to build and O ( n 2 ) O(n^2) O ( n 2 ) space. The algorithm inspects each pair once, when its ≺ \prec ≺ -smaller endpoint is processed, and checks the table in O ( 1 ) O(1) O ( 1 ) time. This takes O ( n 2 ) O(n^2) O ( n 2 ) time in total. When the algorithm starts processing p p p , it extracts from the list of p p p the points z ⪰ p z \succeq p z ⪰ p , in O ( n ) O(n) O ( n ) time. In a step with anchor { p , q } \{p,q\} { p , q } , the points of B ( q , ε D ) \mathbb{B}(q,\varepsilon D) B ( q , ε D ) form a prefix of the list of q q q , and the points z ⪰ p z \succeq p z ⪰ p of B ( p , ε D ) \mathbb{B}(p,\varepsilon D) B ( p , ε D ) form a prefix of this extracted list. The step scans these two prefixes and assigns each point to its piece in O ( 1 ) O(1) O ( 1 ) time (in the real RAM model, since the sector boundaries have irrational slopes), so it takes O ( 1 + m ) O(1+m) O ( 1 + m ) time, where m m m is the number of scanned points. Every scanned point lies in an output dumbbell of the step: a point of A i A_i A i together with the piece C k C_k C k that contains q q q , and a point of C k C_k C k together with the piece A i A_i A i that contains p p p . Hence m ≤ ∑ ( ∣ A ∣ + ∣ C ∣ ) m \leq\sum(|A|+|C|) m ≤ ∑ ( ∣ A ∣ + ∣ C ∣ ) , where the sum is over the output dumbbells { A , C } \{A,C\} { A , C } of the step. Marking the pairs covered by { A , C } \{A,C\} { A , C } takes O ( ∣ A ∣ ⋅ ∣ C ∣ ) O(|A| \cdot|C|) O ( ∣ A ∣ ⋅ ∣ C ∣ ) time, and ∣ A ∣ + ∣ C ∣ ≤ ∣ A ∣ ⋅ ∣ C ∣ + 1 |A|+|C| \leq|A| \cdot|C|+1 ∣ A ∣ + ∣ C ∣ ≤ ∣ A ∣ ⋅ ∣ C ∣ + 1 . Since a step outputs at most 40 dumbbells, all steps together take time linear in the number of steps plus the total number of pair markings. There are at most ( n 2 ) \binom{n}{2} ( 2 n ) steps, and by Lemma 6 every pair is marked at most 360 times, so all steps take O ( n 2 ) O(n^2) O ( n 2 ) time. Sorting dominates the time, and the table and the lists the space.
Dependence on ε \varepsilon ε . The bound of Theorem 3 can also be stated in terms of ε \varepsilon ε . By Observation 5, the number of steps is at most O P T ε = O ( n / ε 2 ) \mathrm{OPT}_{\varepsilon} = O(n/\varepsilon^2) OPT ε = O ( n / ε 2 ) by the CK construction [7 ] . Hence, even if every step scans all of P P P without sorting, the sweep takes O ( n 2 / ε 2 ) O(n^2/\varepsilon^2) O ( n 2 / ε 2 ) time. Together with Theorem 3, this gives O ( n 2 min { log n , 1 / ε 2 } ) O(n^2 \min\{\log n, 1/\varepsilon^2\}) O ( n 2 min { log n , 1/ ε 2 }) time.
Practical Algorithms
We present a greedy variant of the sweep (§ 3.1 ), and we use local search in two ways: to reduce the size of a given WSPD (§ 3.2 ), and to enlarge the lower bound given by the steps of the sweep (§ 3.3 ). They give large practical improvements, but do not improve the approximation bounds.
Greedy Sweep
The proofs of validity and of the approximation factor in Theorem 3 use only one property of a step with anchor { p , q } \{p,q\} { p , q } : it covers R p q R_{pq} R pq . This set contains { p , q } \{p,q\} { p , q } itself and, by the invariant, every uncovered pair covered by an optimal dumbbell that covers { p , q } \{p,q\} { p , q } . Therefore, these two proofs hold verbatim if each step outputs any collection of ε \varepsilon ε -separated dumbbells covering R p q R_{pq} R pq whose size is at most that of the fixed collection. The running-time analysis does not carry over, and we analyze the greedy variant separately below.
The sweep of Theorem 3 , which we call the fixed sweep , is of theoretical interest only: every step outputs a dumbbell for every two nonempty pieces, even if a single dumbbell covers R p q R_{pq} R pq . The greedy sweep keeps the proof but not the collection. It covers R p q R_{pq} R pq with dumbbells grown from pairs of R p q R_{pq} R pq , and falls back to the fixed collection only when that collection is smaller. To grow a dumbbell from a seed pair { a , b } \{a,b\} { a , b } , we start from { { a } , { b } } \{\{a\},\{b\}\} {{ a } , { b }} and repeatedly add a point that fits , that is, a point whose distance to every point of one side is at most ε ∥ a b ∥ \varepsilon\lVert ab\rVert ε ∥ ab ∥ and whose distance to every point of the other side is at least ∥ a b ∥ \lVert ab\rVert ∥ ab ∥ ; the point joins the first side. The dumbbell remains ε \varepsilon ε -separated, with { a , b } \{a,b\} { a , b } as a closest cross pair. Among the points that fit, we choose one that maximizes the number of newly covered pairs of R p q R_{pq} R pq , breaking ties by the number of newly covered pairs overall, and we stop when no point fits. If ∣ R p q ∣ ≤ 16 |R_{pq}|\le16 ∣ R pq ∣ ≤ 16 , the step grows one dumbbell from each pair of R p q R_{pq} R pq and covers R p q R_{pq} R pq by greedy set cover over these candidates. Otherwise, it grows a dumbbell from { p , q } \{p,q\} { p , q } , and then repeatedly grows a dumbbell from the closest pair of R p q R_{pq} R pq that is not yet covered, until R p q R_{pq} R pq is covered. The second rule avoids growing ∣ R p q ∣ |R_{pq}| ∣ R pq ∣ dumbbells when R p q R_{pq} R pq is large. For ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , the number of dumbbells grown in a step is capped at 40. If R p q R_{pq} R pq is not covered by then, the step outputs the fixed collection. The cap does not change the output: a greedy cover with more than 40 dumbbells is larger than the fixed collection, which has at most 40 dumbbells, so the step would output the fixed collection anyway. Finally, the greedy sweep deletes, one at a time, the dumbbells whose pairs are all covered by other dumbbells.
Theorem 7. For P ⊂ R 2 P\subset\mathbb{R}^{2} P ⊂ R 2 and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , the greedy sweep performs at most OPT ε \operatorname{OPT}_{\varepsilon} OPT ε steps and outputs an ε \varepsilon ε -WSPD of size at most 40 OPT ε 40\operatorname{OPT}_{\varepsilon} 40 OPT ε in O ( n 3 ) O(n^{3}) O ( n 3 ) time and O ( n 2 ) O(n^{2}) O ( n 2 ) space.
Proof. Grown dumbbells are ε \varepsilon ε -separated by construction, and every step covers R p q R_{pq} R pq with at most 40 dumbbells, so the size bounds follow as explained above. The running time is proved below.
We prove the time and space bounds of Theorem 7 . The proof holds in every dimension. Let λ = 17 / 8 \lambda=17/8 λ = 17/8 . For a step with anchor { p , q } \{p,q\} { p , q } and D = ∥ p q ∥ D=\lVert pq\rVert D = ∥ pq ∥ , let B p = P ∩ B ( p , λ ε D ) B_p=P\cap\mathbb{B}(p,\lambda\varepsilon D) B p = P ∩ B ( p , λ ε D ) and B q = P ∩ B ( q , λ ε D ) B_q=P\cap\mathbb{B}(q,\lambda\varepsilon D) B q = P ∩ B ( q , λ ε D ) . All the work of the step takes place in these two sets. Indeed, every seed { a , b } \{a,b\} { a , b } is { p , q } \{p,q\} { p , q } or a pair of R p q R_{pq} R pq , so some ε \varepsilon ε -separated dumbbell covers both { a , b } \{a,b\} { a , b } and { p , q } \{p,q\} { p , q } , and its distance is at most D D D . By Observation 2, we may name the seed so that a ∈ B ( p , ε D ) a\in\mathbb{B}(p,\varepsilon D) a ∈ B ( p , ε D ) , b ∈ B ( q , ε D ) b\in\mathbb{B}(q,\varepsilon D) b ∈ B ( q , ε D ) , and ∥ a b ∥ ≤ ( 1 + 2 ε ) D \lVert ab\rVert\le(1+2\varepsilon)D ∥ ab ∥ ≤ ( 1 + 2 ε ) D . A point that fits is within distance ε ∥ a b ∥ \varepsilon\lVert ab\rVert ε ∥ ab ∥ of a a a or b b b , hence within distance ε ( 2 + 2 ε ) D ≤ λ ε D \varepsilon(2+2\varepsilon)D\le\lambda\varepsilon D ε ( 2 + 2 ε ) D ≤ λ ε D of p p p or q q q . Therefore, every pair of R p q R_{pq} R pq and every dumbbell that the step grows or outputs has one side in B p B_p B p and the other in B q B_q B q . The next lemma extends the second part of Lemma 6 to these larger disks.
Lemma 8. Let P ⊂ R d P\subset\mathbb{R}^{d} P ⊂ R d , ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , and λ = 17 / 8 \lambda=17/8 λ = 17/8 . Every pair { x , y } \{x,y\} { x , y } satisfies x ∈ B ( p , λ ε D ) x\in\mathbb{B}(p,\lambda\varepsilon D) x ∈ B ( p , λ ε D ) and y ∈ B ( q , λ ε D ) y\in\mathbb{B}(q,\lambda\varepsilon D) y ∈ B ( q , λ ε D ) , where D = ∥ p q ∥ D=\lVert pq\rVert D = ∥ pq ∥ , for the anchors { p , q } \{p,q\} { p , q } of at most 2 ⋅ 11 2 d 2\cdot11^{2d} 2 ⋅ 1 1 2 d steps of the greedy sweep, in one of the two orders of p p p and q q q .
Proof. Let L = ∥ x y ∥ L=\lVert xy\rVert L = ∥ x y ∥ . Consider the steps with anchors { p j , q j } \{p_j,q_j\} { p j , q j } such that x ∈ B ( p j , λ ε D j ) x\in\mathbb{B}(p_j,\lambda\varepsilon D_j) x ∈ B ( p j , λ ε D j ) and y ∈ B ( q j , λ ε D j ) y\in\mathbb{B}(q_j,\lambda\varepsilon D_j) y ∈ B ( q j , λ ε D j ) , where D j = ∥ p j q j ∥ D_j=\lVert p_jq_j\rVert D j = ∥ p j q j ∥ ; the steps with the roles of x x x and y y y exchanged are counted in the same way. By the triangle inequality, L ≥ ( 1 − 2 λ ε ) D j L\ge(1-2\lambda\varepsilon)D_j L ≥ ( 1 − 2 λ ε ) D j , so p j ∈ B ( x , r ) p_j\in\mathbb{B}(x,r) p j ∈ B ( x , r ) and q j ∈ B ( y , r ) q_j\in\mathbb{B}(y,r) q j ∈ B ( y , r ) , where r = λ ε L / ( 1 − 2 λ ε ) r=\lambda\varepsilon L/(1-2\lambda\varepsilon) r = λ ε L / ( 1 − 2 λ ε ) . Since λ ε ≤ 17 / 128 < 1 / 4 \lambda\varepsilon\le17/128<1/4 λ ε ≤ 17/128 < 1/4 , we have 2 r < L 2r<L 2 r < L , so these two balls are disjoint. The greedy sweep covers R p q R_{pq} R pq in every step, so by Observation 5 , the dumbbell { { p j , p k } , { q j , q k } } \{\{p_j,p_k\},\{q_j,q_k\}\} {{ p j , p k } , { q j , q k }} is not ε \varepsilon ε -separated for j ≠ k j\ne k j = k . Its distance is at least L − 2 r L-2r L − 2 r , so
max { ∥ p j p k ∥ , ∥ q j q k ∥ } > s , where s = ε ( L − 2 r ) = r ( 1 − 4 λ ε ) λ ≥ 15 68 r . \max\{\lVert p_jp_k\rVert,\lVert q_jq_k\rVert\}>s,\qquad\text{where }s=\varepsilon(L-2r)=\frac{r(1-4\lambda\varepsilon)}{\lambda}\ge\frac{15}{68}r. max {∥ p j p k ∥ , ∥ q j q k ∥} > s , where s = ε ( L − 2 r ) = λ r ( 1 − 4 λ ε ) ≥ 68 15 r .
Hence the products B ( p j , s / 2 ) × B ( q j , s / 2 ) ⊂ R 2 d B(p_j,s/2) \times B(q_j,s/2) \subset\mathbb{R}^{2d} B ( p j , s /2 ) × B ( q j , s /2 ) ⊂ R 2 d are pairwise disjoint. They are contained in B ( x , r + s / 2 ) × B ( y , r + s / 2 ) B(x,r+s/2) \times B(y,r+s/2) B ( x , r + s /2 ) × B ( y , r + s /2 ) . Comparing volumes, there are at most ( 1 + 2 r / s ) 2 d ≤ ( 151 / 15 ) 2 d < 11 2 d (1+2r/s)^{2d} \le(151/15)^{2d} < 11^{2d} ( 1 + 2 r / s ) 2 d ≤ ( 151/15 ) 2 d < 1 1 2 d such steps.
Proof of the running time in Theorem 7. We store the covered pairs and the sorted lists as in the proof of Theorem 3, in O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) time, and inspect every pair once. Consider a step, and let N = ∣ B p ∣ + ∣ B q ∣ N=|B_p|+|B_q| N = ∣ B p ∣ + ∣ B q ∣ and M = ∣ B p ∣ ⋅ ∣ B q ∣ M=|B_p|\cdot|B_q| M = ∣ B p ∣ ⋅ ∣ B q ∣ . Since λ ε < 1 / 2 \lambda\varepsilon<1/2 λ ε < 1/2 , the sets B p B_p B p and B q B_q B q are disjoint prefixes of the lists of p p p and q q q . Enumerating R p q R_{pq} R pq takes O ( M ) O(M) O ( M ) time, and we mark its pairs in the table, so that membership in R p q R_{pq} R pq is tested in O ( 1 ) O(1) O ( 1 ) time. To grow a dumbbell, we maintain for every point of B p ∪ B q B_p\cup B_q B p ∪ B q whether it fits and how many pairs it would newly cover. When a point joins a side, these values change only by its own contribution, so they are updated in O ( N ) O(N) O ( N ) time, and a dumbbell is grown in O ( N 2 ) O(N^2) O ( N 2 ) time. Its seed is found by scanning R p q R_{pq} R pq in O ( M ) O(M) O ( M ) time. The greedy set cover for ∣ R p q ∣ ≤ 16 |R_{pq}|\le16 ∣ R pq ∣ ≤ 16 takes O ( N ) O(N) O ( N ) time, and marking each of the at most 40 output dumbbells takes O ( M ) O(M) O ( M ) time. Since p ∈ B p p\in B_p p ∈ B p and q ∈ B q q\in B_q q ∈ B q , we have N ≤ 2 M N\le2M N ≤ 2 M , and N ≤ n N\le n N ≤ n , so the step takes O ( N 2 + M ) = O ( n M ) O(N^2+M)=O(nM) O ( N 2 + M ) = O ( n M ) time. By Lemma 8, every pair contributes to M M M in O ( 1 ) O(1) O ( 1 ) steps, so the sum of M M M over all steps is O ( n 2 ) O(n^2) O ( n 2 ) . Hence the greedy sweep runs in O ( n 3 ) O(n^3) O ( n 3 ) time, and the table and the lists take O ( n 2 ) O(n^2) O ( n 2 ) space.
Local Search for Smaller WSPDs
The sweep of Section 2 never revisits a dumbbell once it is output. We now describe a local-search heuristic that tries to reduce the size of any given ε \varepsilon ε -WSPD, for instance the CK WSPD or the output of the sweep. It uses a single move, reshape , and never increases the size. It uses no solver: unlike exact and heuristic set-cover solvers, it never builds the set-cover instance of MINWSPD, whose size limits these solvers in practice (Section 5).
Reshape. A pair is private to a dumbbell of W \mathcal{W} W if that dumbbell is the only one covering it, and a dumbbell without private pairs is redundant and can be deleted. A point p p p can join the side X X X of an ε \varepsilon ε -separated dumbbell { X , Y } \{X,Y\} { X , Y } if p ∉ X ∪ Y p\notin X\cup Y p ∈ / X ∪ Y and { X ∪ { p } , Y } \{X\cup\{p\},Y\} { X ∪ { p } , Y } is still ε \varepsilon ε -separated. Unlike the greedy sweep of Section 3.1, which keeps the closest cross pair fixed, we allow dist ( X ∪ { p } , Y ) \operatorname{dist}(X\cup\{p\},Y) dist ( X ∪ { p } , Y ) to be smaller than dist ( X , Y ) \operatorname{dist}(X,Y) dist ( X , Y ) . To grow a dumbbell, we repeatedly add a point that can join one of its sides, choosing one that newly covers the most pairs private to other dumbbells (ties are broken at random), until no point can join.
The move (Figure 2) is applied to a target dumbbell T ∈ W T\in\mathcal{W} T ∈ W . If T = { X , Y } T=\{X,Y\} T = { X , Y } is redundant, delete it. Otherwise, replace T T T by the subdumbbell spanned by its private pairs , the dumbbell { X ′ , Y ′ } \{X',Y'\} { X ′ , Y ′ } where X ′ ⊆ X X'\subseteq X X ′ ⊆ X and Y ′ ⊆ Y Y'\subseteq Y Y ′ ⊆ Y consist of the endpoints of these pairs, which is ε \varepsilon ε -separated by Observation 4. Grow it, and then delete, one at a time, the dumbbells that the new dumbbell makes redundant. Shrinking T T T first releases the points that lie in no private pair of T T T , and with them most pairs that other dumbbells also cover, so the new dumbbell can grow in a different direction than the old one. Its growth rule favors pairs that are private to other dumbbells, so repeated reshapes tend to make dumbbells redundant.
The targets are taken in passes over W \mathcal{W} W , each in a new random order, until the time budget ends. Deleted dumbbells are skipped, and dumbbells created during a pass wait for the next one. At the end, the remaining redundant dumbbells are deleted.
Large neighborhood search. For comparison, we also use an integer-programming move. The large neighborhood search (LNS ) move removes a target T T T and its k k k nearest dumbbells, which leaves a set U U U of uncovered pairs. It re-covers U U U by a minimum number of dumbbells, chosen among the removed ones and, if ∣ U ∣ ≤ u |U|\le u ∣ U ∣ ≤ u , maximal ε \varepsilon ε -separated dumbbells whose
Vector (PDF)
caption: A reshape of T T T for ε = 1 / 3 \varepsilon= 1/3 ε = 1/3 , showing three dumbbells, each as its two sides and a closest cross pair. (a) With y y y in T T T , x x x cannot join T T T : the right side would be too wide for the smaller distance. (b) The pairs private to T T T (thin lines) span the subdumbbell, and y y y is released. (c) Free growth adds x x x , which covers the pairs private to U U U , so U U U is deleted.
closest cross pair is in U U U , with CPLEX. The change is accepted only if it uses fewer dumbbells than it removes. LNS takes its targets in the same passes as reshape, and its neighborhoods and parameters are given in § 5.1 .
Observation 9. Reshape and LNS keep W \mathcal{W} W an ε \varepsilon ε -WSPD and do not increase ∣ W ∣ |\mathcal{W}| ∣ W ∣ .
Proof. In a reshape, the new dumbbell contains the subdumbbell spanned by the private pairs of T T T , so it covers every pair that only T T T covered. It is ε \varepsilon ε -separated by Observation 4 and because every added point keeps it ε \varepsilon ε -separated. Only redundant dumbbells are deleted, and redundancy is checked again before each deletion, so every pair stays covered. A reshape replaces T T T by one dumbbell and otherwise only deletes dumbbells, so ∣ W ∣ |\mathcal{W}| ∣ W ∣ does not increase. LNS adds ε \varepsilon ε -separated dumbbells that cover U U U , and only if the size decreases.
Implementation. A reshape must decide which pairs are private, which dumbbells become redundant, and which points can join a side, each in constant time per pair or point. A table stores, for every pair, the number of dumbbells of W \mathcal{W} W that cover it. Inserting or deleting { X , Y } \{X,Y\} { X , Y } updates it in O ( ∣ X ∣ ⋅ ∣ Y ∣ ) O(|X|\cdot|Y|) O ( ∣ X ∣ ⋅ ∣ Y ∣ ) time. A pair is private if its count is 1, so finding private pairs, testing redundancy, and computing the gain of a point take O ( 1 ) O(1) O ( 1 ) time per pair. Shrinking T T T and deleting dumbbells only decrease counts, so a dumbbell becomes redundant only if the new T T T covers one of its private pairs. To find it, we need the owner of such a pair, the dumbbell to which it was private. Lists of the dumbbells containing each point are expensive: at n = 10000 n=10000 n = 10000 , a point lies in hundreds to thousands of dumbbells. Instead, a second table stores, for every pair, the bitwise exclusive or of the indices of the dumbbells that cover it, updated in the same loop as the counts. Since k ⊕ k = 0 k \oplus k = 0 k ⊕ k = 0 , deleting a dumbbell cancels its insertion, so for a pair with count 1 the entry is the index of its owner. Hence the dumbbells that become redundant are found while T T T is inserted, at no extra asymptotic cost. In a preliminary test with n = 10000 n=10000 n = 10000 , this made reshape more than an order of magnitude faster than point-to-dumbbell lists. A point that can join X X X satisfies ∥ p x ∥ < ε dist ( X , Y ) \lVert px\rVert< \varepsilon\,\operatorname{dist}(X,Y) ∥ p x ∥ < ε dist ( X , Y ) for every x ∈ X x \in X x ∈ X , so the candidates are the points within distance ε dist ( X , Y ) \varepsilon\,\operatorname{dist}(X,Y) ε dist ( X , Y ) of the initial X X X or Y Y Y , found by range queries in a kd-tree. For ε < 1 / 2 \varepsilon< 1/2 ε < 1/2 , each can join only the side it is close to. Diameters only increase and the distance between the sides only decreases, so a candidate that cannot join is discarded for good. For each candidate, we maintain its largest distance to its side, its smallest distance to the other side, and its gain, so that after each addition, updating them and testing separation exactly take constant time per candidate. The points are relabeled in the order of a Hilbert curve, and the tables are packed upper triangles of ( n 2 ) \binom{n}{2} ( 2 n ) entries of 4 bytes, stored by rows, so the entries of the pairs of a dumbbell are close in memory.
Local Search for Larger Lower Bounds
The compatibility graph G ε G_{\varepsilon} G ε has the pairs as vertices and an edge between any two compatible pairs. By the proof of Observation 5 , every independent set I I I of G ε G_{\varepsilon} G ε gives the lower bound ∣ I ∣ ≤ OPT ε |I| \leq\operatorname{OPT}_{\varepsilon} ∣ I ∣ ≤ OPT ε . The anchors of the greedy sweep form such a set, and we call their number LB 0 \operatorname{LB}_{0} LB 0 . We enlarge this set by a local search for large independent sets, starting from the anchors. For the current set I I I , a pair is free if it has no neighbor in I I I , and tight for e ∈ I e \in I e ∈ I if e e e is its only neighbor in I I I . These terms and the 1-for-2 swaps below follow the local search of Andrade, Resende, and Werneck [1 ] for maximum independent sets. The search has three stages.
Add free pairs to I I I until none is left.
Repeat passes over I I I . For each e ∈ I e \in I e ∈ I , if two pairs f f f and g g g that are tight for e e e are incompatible with each other, replace e e e by f f f and g g g (a 1-for-2 swap ), and add the pairs that have become free. Stop after a pass without swaps, and let LB 1 = ∣ I ∣ \operatorname{LB}_{1} = |I| LB 1 = ∣ I ∣ .
Make 30 more passes in which, in addition, a pair e e e without a swap is replaced, with probability 1 / 2 1/2 1/2 , by a random pair that is tight for e e e , followed again by the free pairs. These plateau moves [18 , 13 ] do not change ∣ I ∣ |I| ∣ I ∣ , but they change which pairs are tight, so later passes find new swaps. The lower bound LB \operatorname{LB} LB is ∣ I ∣ |I| ∣ I ∣ at the end.
A pair joins I I I only if it is free or tight for the leaving pair, so I I I stays independent and LB 0 ≤ LB 1 ≤ LB ≤ OPT ε \operatorname{LB}_{0} \leq\operatorname{LB}_{1} \leq\operatorname{LB} \leq\operatorname{OPT}_{\varepsilon} LB 0 ≤ LB 1 ≤ LB ≤ OPT ε .
Implementation. The search keeps a table with, for every pair w w w , the number t ( w ) t(w) t ( w ) of pairs of I I I compatible with w w w . Hence w w w is free if t ( w ) = 0 t(w) = 0 t ( w ) = 0 , and tight for e e e if t ( w ) = 1 t(w) = 1 t ( w ) = 1 and w w w is compatible with e e e . If { x ′ , y ′ } \{x',y'\} { x ′ , y ′ } is compatible with e = { x , y } e = \{x,y\} e = { x , y } , then, by Observations 2 and 4 and after possibly exchanging x ′ x' x ′ and y ′ y' y ′ , we have x ′ ∈ B ( x , ε ∥ x y ∥ ) x' \in B(x,\varepsilon\lVert xy\rVert) x ′ ∈ B ( x , ε ∥ x y ∥) and y ′ ∈ B ( y , ε ∥ x y ∥ ) y' \in B(y,\varepsilon\lVert xy\rVert) y ′ ∈ B ( y , ε ∥ x y ∥) . As in the proof of Theorem 3 , these points are prefixes of the lists of the points sorted by distance from x x x and from y y y , which gives the enumeration, and the update of the table when e e e joins or leaves I I I , in O ( M e ) O(M_e) O ( M e ) time, where M e M_e M e is the product of the numbers of points in the two disks. In a pass, we skip e e e if the dumbbell formed by the first points and the second points of the tight pairs of e e e , oriented as above, is ε \varepsilon ε -separated: then all these pairs are pairwise compatible by Observation 4 . Otherwise, we test pairs of tight pairs for compatibility, at most 2 ⋅ 10 5 2 \cdot10^5 2 ⋅ 1 0 5 of them per e e e and pass. Because of this limit, LB 1 \operatorname{LB}_{1} LB 1 need not be a local optimum for 1-for-2 swaps.
Proposition 10. Let ε ≤ 1 / 16 \varepsilon\leq1/16 ε ≤ 1/16 . The search takes O ( n 2 log n + k n 3 ) O(n^2 \log n + kn^3) O ( n 2 log n + k n 3 ) time and O ( n 2 ) O(n^2) O ( n 2 ) space, where k k k is the number of passes, and k ≤ LB 1 − LB 0 + 31 k \leq\operatorname{LB}_{1} - \operatorname{LB}_{0} + 31 k ≤ LB 1 − LB 0 + 31 .
Proof. Sorting takes O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) time, and the lists and the table take O ( n 2 ) O(n^2) O ( n 2 ) space. The first stage scans all pairs once, and it adds pairs to I I I without removing any, so its updates take O ( ∑ e ∈ I M e ) O(\sum_{e \in I} M_e) O ( ∑ e ∈ I M e ) time for the final set I I I . The second part of the proof of Lemma 2 uses only that the anchors are pairwise incompatible. Applied to I I I , it shows that every pair lies in the product of the two disks of at most 360 pairs of I I I , so ∑ e ∈ I M e = O ( n 2 ) \sum_{e \in I} M_e = O(n^2) ∑ e ∈ I M e = O ( n 2 ) for every pairwise incompatible set I I I . In a pass, the pairs processed were in I I I when the pass started, and the pairs added during the pass stay in I I I until it ends, so enumerations and updates take O ( n 2 ) O(n^2) O ( n 2 ) time in all. The test that skips e e e takes time quadratic in the number N e N_e N e of points in the two disks, and N e 2 ≤ 2 n M e N_e^2 \leq2nM_e N e 2 ≤ 2 n M e as in the proof of Theorem 7 , which gives O ( n 3 ) O(n^3) O ( n 3 ) per pass. The tests of pairs of tight pairs take O ( 1 ) O(1) O ( 1 ) time per pair of I I I . Every pass of the second stage except the last increases ∣ I ∣ |I| ∣ I ∣ , so there are at most LB 1 − LB 0 + 31 \operatorname{LB}_{1} - \operatorname{LB}_{0} + 31 LB 1 − LB 0 + 31 passes.
In the experiments, stage 2 makes at most 13 passes, and the time grows like n 2 n^2 n 2 (Figure 4 ).
Figure 4. The lower bounds of Section 3.3: means over the instances.
Sweep in Higher Dimensions
In this section, P ⊂ R d P \subset\mathbb{R}^{d} P ⊂ R d for a fixed d ≥ 3 d \ge3 d ≥ 3 , and B ( c , ρ ) B(c,\rho) B ( c , ρ ) denotes a closed ball. The order ≺ \prec ≺ is the lexicographic order on R d \mathbb{R}^{d} R d , and the half-ball B + ( c , ρ ) B^{+}(c,\rho) B + ( c , ρ ) consists of the points of B ( c , ρ ) B(c,\rho) B ( c , ρ ) whose first coordinate is at least that of c c c . Constants in the O O O -notation may depend on d d d . The local search does not depend on the dimension; § 5.3 reports experiments in R 3 \mathbb{R}^{3} R 3 .
Theorem 11. Let d ≥ 3 d \ge3 d ≥ 3 be fixed and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 . There are pieces for which, for every P ⊂ R d P \subset\mathbb{R}^{d} P ⊂ R d , the sweep performs at most OPT ε \operatorname{OPT}_{\varepsilon} OPT ε steps and outputs an ε \varepsilon ε -WSPD of size less than 32 d OPT ε 32^{d}\operatorname{OPT}_{\varepsilon} 3 2 d OPT ε , and at most 2048 OPT ε 2048\operatorname{OPT}_{\varepsilon} 2048 OPT ε if d = 3 d=3 d = 3 , in O ( n 2 log n ) O(n^{2}\log n) O ( n 2 log n ) time and O ( n 2 ) O(n^{2}) O ( n 2 ) space. With the same pieces, the greedy sweep satisfies the same bounds, except that it runs in O ( n 3 ) O(n^{3}) O ( n 3 ) time.
What carries over. Observations 2 and 4 hold in every dimension. The proof of Theorem 3 uses three properties of the pieces: they partition the ball and the half-ball, they have diameter at most ( 1 − 2 ε ) (1-2\varepsilon) ( 1 − 2 ε ) times the radius, and there are 8 pieces in the ball and 5 in the half-ball. The invariant and the charging also use that a point x ⪰ p x \succeq p x ⪰ p of B ( p , ε D ) B(p,\varepsilon D) B ( p , ε D ) lies in B + ( p , ε D ) B^{+}(p,\varepsilon D) B + ( p , ε D ) , which holds for the lexicographic order in any dimension. Hence, if the ball and the half-ball of radius ρ \rho ρ are partitioned into k k k and h h h pieces, respectively, each of diameter at most ( 1 − 2 ε ) ρ (1-2\varepsilon)\rho ( 1 − 2 ε ) ρ , the proofs of validity and of the approximation factor apply verbatim and give an ε \varepsilon ε -WSPD of size at most k h OPT ε kh\operatorname{OPT}_{\varepsilon} k h OPT ε . Observation 5 does not use the geometry of the pieces, and it holds as stated: the number of steps is a lower bound on OPT ε \operatorname{OPT}_{\varepsilon} OPT ε . The same holds for the greedy sweep, whose cap of 40 becomes k h kh k h .
Pieces. Let δ = 7 / 8 \delta=7/8 δ = 7/8 , so that δ ≤ 1 − 2 ε \delta\le1-2\varepsilon δ ≤ 1 − 2 ε for ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 . It suffices to partition B ( 0 , 1 ) B(0,1) B ( 0 , 1 ) and B + ( 0 , 1 ) B^{+}(0,1) B + ( 0 , 1 ) into pieces of diameter at most δ \delta δ , and to scale and translate them to B ( c , ρ ) B(c,\rho) B ( c , ρ ) and B + ( c , ρ ) B^{+}(c,\rho) B + ( c , ρ ) . For fixed d d d , the pieces below are fixed sets, and a point is assigned to its piece in O ( 1 ) O(1) O ( 1 ) time.
The grid pieces: let m d = ⌈ 8 d / 7 ⌉ m_d=\lceil8\sqrt{d}/7\rceil m d = ⌈ 8 d /7 ⌉ , partition the bounding cube of B ( 0 , 1 ) B(0,1) B ( 0 , 1 ) into the ( 2 m d ) d (2m_d)^d ( 2 m d ) d cubes of side 1 / m d 1/m_d 1/ m d of a grid, and intersect them with the ball. The hyperplane through 0 orthogonal to the first axis is a grid hyperplane, so the half-ball meets only m d ( 2 m d ) d − 1 m_d(2m_d)^{d-1} m d ( 2 m d ) d − 1 of these cubes. Each cube has diameter d / m d ≤ δ \sqrt{d}/m_d \le\delta d / m d ≤ δ . Hence k = ( 2 m d ) d k=(2m_d)^d k = ( 2 m d ) d , h = m d ( 2 m d ) d − 1 h=m_d(2m_d)^{d-1} h = m d ( 2 m d ) d − 1 , and k h = 2 2 d − 1 m d 2 d kh=2^{2d-1}m_d^{2d} k h = 2 2 d − 1 m d 2 d . For d = 3 d=3 d = 3 , we have m 3 = 2 m_3=2 m 3 = 2 , with 64 pieces in the ball and 32 in the half-ball, and k h = 2048 kh=2048 k h = 2048 . For d = 4 d=4 d = 4 , we have m 4 = 3 m_4=3 m 4 = 3 and k h = 839808 < 32 4 kh=839808<32^{4} k h = 839808 < 3 2 4 . A point is assigned to its cube by rounding its coordinates down, and a coordinate equal to 1 is assigned to the last cube.
The net pieces: let G G G be the set of points of the grid η Z d \eta\mathbb{Z}^{d} η Z d , with η = δ / ( 400 d ) \eta=\delta/(400\sqrt{d}) η = δ / ( 400 d ) , at distance at most $1+\delta/800$ from the origin, and let N N N be a maximal subset of G G G whose points are pairwise more than 399 δ / 800 399\delta/800 399 δ /800 apart, found greedily. Every point of B ( 0 , 1 ) B(0,1) B ( 0 , 1 ) is within distance δ / 800 \delta/800 δ /800 of G G G , and by maximality every point of G G G is within distance 399 δ / 800 399\delta/800 399 δ /800 of N N N , so every point of B ( 0 , 1 ) B(0,1) B ( 0 , 1 ) is within distance δ / 2 \delta/2 δ /2 of N N N . Hence assigning every point to a nearest point of N N N (ties broken by a fixed order of N N N ) partitions the ball, and the half-ball, into at most ∣ N ∣ |N| ∣ N ∣ pieces of diameter at most δ \delta δ . The balls of radius 399 δ / 1600 c e n t e r e d a t 399\delta/1600 centered at 399 δ /1600 ce n t er e d a t N$ are pairwise disjoint and contained in B ( 0 , 1 + 401 δ / 1600 ) B(0,1+401\delta/1600) B ( 0 , 1 + 401 δ /1600 ) , so ∣ N ∣ ≤ ( 1600 / ( 399 δ ) + 401 / 399 ) d = ( 15607 / 2793 ) d < 5.59 d |N| \le(1600/(399\delta)+401/399)^{d}=(15607/2793)^{d}<5.59^{d} ∣ N ∣ ≤ ( 1600/ ( 399 δ ) + 401/399 ) d = ( 15607/2793 ) d < 5.5 9 d . Hence k h < 5.59 2 d < 31.25 d < 32 d kh<5.59^{2d}<31.25^{d}<32^{d} k h < 5.5 9 2 d < 31.2 5 d < 3 2 d , which is smaller than the factor of the grid pieces for d ≥ 5 d\ge5 d ≥ 5 . The set N N N depends only on d d d , and a point is assigned to its piece in O ( ∣ N ∣ ) = O ( 1 ) O(|N|)=O(1) O ( ∣ N ∣ ) = O ( 1 ) time.
Lemma 12. Let ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 and d ≥ 2 d \ge2 d ≥ 2 . Every pair is covered by the output dumbbells of at most 2 ( 11 / 3 ) 2 d 2(11/3)^{2d} 2 ( 11/3 ) 2 d steps of the sweep in R d \mathbb{R}^{d} R d , and by at most one output dumbbell of each step.
Proof. The proof of Lemma 6 applies verbatim, with balls in place of disks and volumes in R 2 d \mathbb{R}^{2d} R 2 d in place of the products of areas. The products B ( p j , s / 2 ) × B ( q j , s / 2 ) ⊂ R 2 d B(p_j,s/2) \times B(q_j,s/2) \subset\mathbb{R}^{2d} B ( p j , s /2 ) × B ( q j , s /2 ) ⊂ R 2 d are pairwise disjoint and contained in B ( x , r + s / 2 ) × B ( y , r + s / 2 ) B(x,r+s/2) \times B(y,r+s/2) B ( x , r + s /2 ) × B ( y , r + s /2 ) , so each of the two classes has at most ( 1 + 2 r / s ) 2 d ≤ ( 11 / 3 ) 2 d (1+2r/s)^{2d} \le(11/3)^{2d} ( 1 + 2 r / s ) 2 d ≤ ( 11/3 ) 2 d steps.
Proof of Theorem 11 . The size bounds follow from the discussion above, with the grid pieces for d ≤ 4 d \le4 d ≤ 4 and the net pieces for d ≥ 5 d \ge5 d ≥ 5 . The proof of the running time in Theorem 3 applies verbatim, with Lemma 12 in place of Lemma 6 , since a point is assigned to its piece in O ( 1 ) O(1) O ( 1 ) time. For the greedy sweep, whose cap of 40 becomes k h k_h k h , the bounds on the number of steps and the size also follow from the discussion above, and the proof of its running time applies verbatim, with Lemma 8 in R d \mathbb{R}^d R d , and gives O ( n 3 ) O(n^3) O ( n 3 ) time and O ( n 2 ) O(n^2) O ( n 2 ) space.
As in the plane, the number of steps is at most O P T ε = O ( n / ε d ) \mathrm{OPT}_{\varepsilon} = O(n/\varepsilon^d) OPT ε = O ( n / ε d ) [7 ] , so the sweep also runs in O ( n 2 / ε d ) O(n^2/\varepsilon^d) O ( n 2 / ε d ) time.
Dependence on d d d . The factor of the grid pieces grows as d Θ ( d ) d^{\Theta(d)} d Θ ( d ) , and that of the net pieces as 2 O ( d ) 2^{O(d)} 2 O ( d ) . No choice of pieces can make this analysis subexponential in d d d . By the isodiametric inequality, a piece of diameter at most ( 1 − 2 ε ) ρ (1-2\varepsilon)\rho ( 1 − 2 ε ) ρ has at most a ( ( 1 − 2 ε ) / 2 ) d ((1-2\varepsilon)/2)^d (( 1 − 2 ε ) /2 ) d fraction of the volume of the ball, so k h ≥ 2 2 d − 1 / ( 1 − 2 ε ) 2 d > 2 2 d − 1 k_h \ge2^{2d-1}/(1-2\varepsilon)^{2d} > 2^{2d-1} k h ≥ 2 2 d − 1 / ( 1 − 2 ε ) 2 d > 2 2 d − 1 .
Experiments
We address the following questions. (Q1) How close to optimal are the greedy sweep and the CK WSPD, and how does the gap depend on the input and n n n ? (Q2) What are the running times? (Q3) Can local search close the remaining gap, and how does it compare with LNS? (Q4) How large are partition WSPDs converted from cover WSPDs, compared with those built directly? We use ε = 1 / 20 \varepsilon= 1/20 ε = 1/20 (Theorem 3 needs ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 ). Sections 5.1 and 5.2 treat points in the plane and Section 5.3 points in R 3 \mathbb{R}^3 R 3 .
Setup
All algorithms are implemented in C++. Points have integer coordinates and ε \varepsilon ε is rational, so all separation tests are exact, and every output is checked by a separate brute-force verifier. We compare three algorithms. The sweep is the greedy sweep of § 3.1 followed by a pass that removes redundant dumbbells. CK is the variant of the CK construction on a fair split tree [7 ] that accepts two nodes if their point sets are ε \varepsilon ε -separated, and CK box tests the bounding boxes of the two nodes instead, so it outputs at least as many dumbbells. The inputs (Figure 3 ) are six synthetic families (uniform, Gaussian, clustered, perturbed grid, logarithmic spiral, and annulus) and the non-uniform instances of the CG:SHOP 2019 challenge [10 ] , for n n n from 200 to 50000. Code, generators, and raw results are available at https://github.com/gfonsecabr/small-wspd-experiments. Table 2 gives the local search over time, Table 3 the mean size divided by the reference (§ 5.2 ) for every input and n ∈ { 1000 , 10000 , 50000 } n \in\{1000, 10000, 50000\} n ∈ { 1000 , 10000 , 50000 } , and Table 4 the same for the partition WSPDs of Q4 and n ∈ { 1000 , 10000 } n \in\{1000, 10000\} n ∈ { 1000 , 10000 } . The rest of this subsection gives the details.
Figure 3. Synthetic and CG:SHOP instances for n = 1000 n = 1000 n = 1000 .
Table 2. Table 2 Local search over time: mean size divided by the reference. Build time : median time to build the start, not included in the times. Bold: best value for each n n n and time over both starts.
Table 3. Table 3 Mean size divided by the reference, per input: synthetic inputs (three seeds for n ≤ 10000 n \le10000 n ≤ 10000 , one for n = 50000 n = 50000 n = 50000 ) and CG:SHOP 2019 families. †: the reference is the lower bound. Bold: smallest construction of the row.
Table 4. Partition WSPDs: mean size divided by the reference (†: the lower bound) per input and n n n . First column: the cover WSPD of the sweep followed by reshape. The others are partition WSPDs: its conversion and CK, each without and with the merge pass, and the deterministic quadtree with exact separation tests and the merge pass. Bold: smallest partition WSPD of the row.
Measurements. All experiments ran on an AMD Ryzen 9 9900X (12 cores, 128 GB of RAM, Fedora Linux 44, GCC 16.2 with -O2), with up to 11 single-threaded runs in parallel and no other load. Times are wall-clock. Memory is the peak resident set size of a run, which includes the output and the verifier. All methods, including CK, store every dumbbell as two lists of points, so the times of CK include listing these points, which the time bounds of § 7 do not. In Figure 8 , the time to 1.001 OPT is the mean over the inputs with proven OPT, and where CPLEX reached its time limit of 1800 s on some input, the mean time of CPLEX is a lower bound.
Figure 8. Mean running time and largest peak memory.
Implementation. The implementation uses the Pangolin geometry library [9 ] . With ε = a / b \varepsilon= a/b ε = a / b , the separation test is b 2 diam ( X ) 2 ≤ a 2 dist ( X , Y ) 2 b^2 \operatorname{diam}(X)^2 \le a^2 \operatorname{dist}(X,Y)^2 b 2 diam ( X ) 2 ≤ a 2 dist ( X , Y ) 2 , and the verifier checks coverage and exact separation.
Sweep. The final pass that removes redundant dumbbells considers them in the order of increasing ∣ X ∣ ⋅ ∣ Y ∣ |X| \cdot|Y| ∣ X ∣ ⋅ ∣ Y ∣ . For each p p p , the sweep processes the points q ≻ p q \succ p q ≻ p by increasing distance from p p p . It stores one byte per pair, so memory is quadratic in n n n (Figure 8 ). When a step falls back to the fixed collection, it assigns the points to the pieces in floating point, which matters only for points on a boundary between pieces, and the output is verified like every other.
CK. The recursive construction on a fair split tree [7 ] , which splits the longer side of the bounding box of a node at its midpoint. When two nodes are not accepted, the recursion splits the one whose bounding box has the larger diameter. CK box accepts two nodes if the diameters of their boxes are at most ε \varepsilon ε times the distance between the boxes, and CK tests the point sets exactly when this test fails. These are the two variants of Theorem 20 . The original construction [7 ] tests balls that contain the boxes and splits the node whose box has the longer side (§ 7 ). Both variants are partition WSPDs, so the redundancy pass would not change them.
Exact optimum. An ε \varepsilon ε -separated dumbbell { X , Y } \{X,Y\} { X , Y } with dist ( X , Y ) = ∥ p q ∥ \operatorname{dist}(X,Y) = \lVert pq\rVert dist ( X , Y ) = ∥ pq ∥ , p ∈ X p \in X p ∈ X , and q ∈ Y q \in Y q ∈ Y corresponds to a clique containing p p p and q q q in an auxiliary graph on the points of B ( p , ε ∥ p q ∥ ) ∪ B ( q , ε ∥ p q ∥ ) B(p,\varepsilon\lVert pq\rVert) \cup B(q,\varepsilon\lVert pq\rVert) B ( p , ε ∥ pq ∥) ∪ B ( q , ε ∥ pq ∥) . The edges of this graph encode the pairwise conditions ∥ x x ′ ∥ ≤ ε ∥ p q ∥ \lVert xx'\rVert\le\varepsilon\lVert pq\rVert ∥ x x ′ ∥ ≤ ε ∥ pq ∥ , ∥ y y ′ ∥ ≤ ε ∥ p q ∥ \lVert yy'\rVert\le\varepsilon\lVert pq\rVert ∥ y y ′ ∥ ≤ ε ∥ pq ∥ , and ∥ x y ∥ ≥ ∥ p q ∥ \lVert xy\rVert\ge\lVert pq\rVert ∥ x y ∥ ≥ ∥ pq ∥ . We enumerate all maximal cliques (Bron–Kerbosch [4 ] ) for every choice of p p p and q q q , and solve the resulting set-cover problem by integer programming with CPLEX 22.2. This is exact because some minimum WSPD consists of maximal dumbbells, and every maximal dumbbell arises from a maximal clique. Where CPLEX proves optimality for n = 1000 n = 1000 n = 1000 (10 of the 22 instances), the set-cover instance has a median of 6.6 ⋅ 10 5 6.6 \cdot10^5 6.6 ⋅ 1 0 5 maximal dumbbells. For the spirals with n ≥ 800 n \ge800 n ≥ 800 , we first apply exact set-cover reductions (forced columns, row and column dominance) until none applies, and then run CPLEX on one connected component at a time, with three threads and the sweep followed by reshape as a warm start. For n = 1000 n = 1000 n = 1000 , OPT is thus known on 13 instances.
Lower bound. The lower bounds come from separate runs of the sweep, which write the anchors to a file, followed by the search of § 3.3 , a separate program, with up to 9 runs in parallel for n ≤ 10000 n \le10000 n ≤ 10000 and 4 for larger n n n . The plateau moves use one fixed random seed. In Figure 4 , panel (a) shows the mean over the instances with proven OPT (all of them for n ≤ 500 n \le500 n ≤ 500 ), panel (b) the mean over all instances, and panel (c) the mean running time of these runs, including the sweep. We computed the independence number α \alpha α of G ε G_{\varepsilon} G ε for every instance with n ≤ 500 n \le500 n ≤ 500 by integer programming with CPLEX: one 0/1 variable per pair, whose sum is maximized, with at most one chosen pair in every maximal dumbbell, since two pairs are compatible if and only if some maximal dumbbell covers both. CPLEX proves optimality on all 88 instances, in at most 2 min each.
Local search. Every run uses one fixed random seed. For LNS, the scale of a dumbbell { X , Y } \{X,Y\} { X , Y } is dist ( X , Y ) \operatorname{dist}(X,Y) dist ( X , Y ) . The neighborhood of a dumbbell T = { A , B } T = \{A,B\} T = { A , B } with scale ℓ T \ell_T ℓ T consists of the dumbbells Z Z Z that contain a point within distance 2 ε ℓ T 2\varepsilon\ell_T 2 ε ℓ T of a point of T T T , whose scale is within a factor ( 1 + 2 ε ) 2 (1 + 2\varepsilon)^2 ( 1 + 2 ε ) 2 of ℓ T \ell_T ℓ T , and whose sides, in one of the two orientations, have centroids within distance 2 ε ℓ T 2\varepsilon\ell_T 2 ε ℓ T of the centroids of A A A and B B B . Neighbors are ranked by the larger of these two centroid distances, and LNS removes T T T and its k k k nearest neighbors. The candidate dumbbells for a pair of U U U are the first 300 found by the enumeration used to compute OPT (above), and CPLEX has a limit of 2 s per call. We use ( k , u ) = ( 16 , 1000 ) (k,u) = (16, 1000) ( k , u ) = ( 16 , 1000 ) for n ≤ 1000 n \le1000 n ≤ 1000 and ( 32 , 400 ) (32, 400) ( 32 , 400 ) for larger n n n . In Figure 10 , a curve begins at the mean time to build the start, over the instances of an input, and is horizontal while reshape is set up (relabeling the points and building its tables), a time that we measured in separate runs. It then shows the mean size for the same reshape time. Within its budget, LNS makes about 2 ⋅ 10 5 2 \cdot10^{5} 2 ⋅ 1 0 5 moves for n = 10000 n = 10000 n = 10000 and between 8 ⋅ 10 4 8 \cdot10^{4} 8 ⋅ 1 0 4 and 3 ⋅ 10 5 3 \cdot10^{5} 3 ⋅ 1 0 5 for n = 50000 n = 50000 n = 50000 , on WSPDs of 3 ⋅ 10 6 3 \cdot10^{6} 3 ⋅ 1 0 6 to 4 ⋅ 10 7 4 \cdot10^{7} 4 ⋅ 1 0 7 dumbbells, so for large n n n it tries only a small fraction of the dumbbells. The parameters of LNS are the best ones among those we tested on the local-search samples (below) and on three instances with n = 3000 n = 3000 n = 3000 : neighborhoods of radius 1.5 ε ℓ T 1.5\varepsilon\ell_T 1.5 ε ℓ T to 5 ε ℓ T 5\varepsilon\ell_T 5 ε ℓ T , 4 to 64 neighbors, and bounds on ∣ U ∣ |U| ∣ U ∣ from 50 to 4000 and no bound, in all combinations. The limit of CPLEX (0.5 to 10 s) and the number of dumbbells enumerated per pair (50 to 2000) changed the sizes by at most 0.3%.
Figure 10. Mean size / reference per input over the total time: build of the start, then reshape.
Inputs. Synthetic inputs (Figure 3 ) are generated at scale M = 10 6 M = 10^{6} M = 1 0 6 around the center ( M / 2 , M / 2 ) (M/2, M/2) ( M /2 , M /2 ) and rounded to integer coordinates, with three seeds each: uniform in [ 0 , M ] 2 [0,M]^2 [ 0 , M ] 2 ; Gaussian (standard deviation M / 8 M/8 M /8 ); clustered (max { 2 , n / 20 } \max\{2,n/20\} max { 2 , n /20 } uniform centers, each point Gaussian around a random center with standard deviation M / 100 M/100 M /100 ); perturbed grid (a grid with ⌈ n ⌉ \lceil\sqrt{n}\rceil ⌈ n ⌉ columns, each point moved by a Gaussian of standard deviation 2% of the spacing); logarithmic spiral (the point 2000 e t ( cos 3 t , sin 3 t ) 2000e^{t}(\cos3t,\sin3t) 2000 e t ( cos 3 t , sin 3 t ) relative to the center, with t t t uniform in [ 0 , 6 ] [0,6] [ 0 , 6 ] ); and annulus (uniform angle, radius uniform in [ 1 , 1.1 ] ⋅ M / 4 [1,1.1] \cdot M/4 [ 1 , 1.1 ] ⋅ M /4 ). Duplicate points are discarded and replaced. The CG:SHOP 2019 instances [10 ] come from the 2019 Computational Geometry Challenge. We use all of its non-uniform instances whose size is one of the values of n n n below, after removing duplicates. We use n n n from 200 to 1000 in steps of 100, from 2000 to 10000 in steps of 1000, and from 20000 to 50000 in steps of 10000 (one seed). The perturbed grid is filled row by row.
For every n ≤ 10000 n \le10000 n ≤ 10000 , there are 18 synthetic and 4 CG:SHOP instances, and for every n ≥ 20000 n \ge20000 n ≥ 20000 , 6 and 4. The local-search samples are the first seed of every generator and the four CG:SHOP instances for n = 1000 n = 1000 n = 1000 , and the first uniform and clustered instances and one CG:SHOP instance (euro-night) for n = 10000 n = 10000 n = 10000 and n = 50000 n = 50000 n = 50000 . Figure 9 and Table 2 show reshape and LNS on these samples, and Figure 9 also on all instances with n = 200 n = 200 n = 200 . For n = 50000 n = 50000 n = 50000 , both ran for 5000 s.
Figure 9. Local search: mean size / reference over time, on all instances for n = 200 n = 200 n = 200 .
Results
Reference value. We compute OPT as described in § 5.1 . Within 1800 s per instance, CPLEX proves optimality on all instances with n ≤ 500 n \le500 n ≤ 500 and on some with 600 ≤ n ≤ 1000 600 \le n \le1000 600 ≤ n ≤ 1000 , including the spirals with n ≥ 800 n \ge800 n ≥ 800 . Otherwise we compare against the lower bound LB of § 3.3 , so some values of n n n mix both references. Where OPT is known (Figure 4 ), LB is on average 0.999, 0.997, and 0.994 times OPT for n = 200 n = 200 n = 200 , 500, and 1000, at least 0.989 OPT on every instance, and equal to OPT on 7 instances. The number of steps LB0 _0 0 is on average 0.98, 0.97, and 0.94 times OPT, and at least 0.90 OPT, and LB1 _1 1 is in between. For n ≤ 500 n \le500 n ≤ 500 , we computed exactly the independence number α \alpha α of G ε G_\varepsilon G ε , the best bound that independent sets can give: it is at least 0.992 OPT and on average 0.999 OPT. Of the gap between LB0 _0 0 and α \alpha α , the swaps close 76% and the plateau moves another 22%, and LB = α \alpha α on 31 of these 88 instances. Ratios to LB overestimate ratios to OPT, probably more so for larger n n n : LB/LB0 _0 0 grows from 1.05 for n = 1000 n = 1000 n = 1000 to 1.10 and 1.12 for n = 10000 n = 10000 n = 10000 and 50000.
Quality (Q1). Figure 5 summarizes the results, and Figure 6 and Table 3 show them per input. For n = 500 n = 500 n = 500 , the sweep is on average 3% above OPT (at most 9%), and CK box and CK are 21% and 17% above (at most 37% and 27%). For n = 10000 n = 10000 n = 10000 , the sweep is on average at 1.22 LB and CK at 1.55 LB, and for n = 50000 n = 50000 n = 50000 at 1.38 LB and 1.76 LB. Part of this growth may come from the lower bound, whose ratio to OPT decreases with n n n where OPT is known (Figure 4 ). The sweep is smallest, followed by CK and CK box, on every input and for every n n n , except on the perturbed grid, where the three methods are equal for n = 200 n = 200 n = 200 and CK is smaller than the sweep for n = 1000 n = 1000 n = 1000 (by less than 1%) and for n = 4000 n = 4000 n = 4000 (by 4%). After the merge pass of Q4, CK is still larger than the sweep on average for every n n n (1.06 OPT against 1.03 OPT for n = 500 n = 500 n = 500 , and 1.46 LB against 1.22 LB for $n = 10000). Figure 7 gives the number of dumbbells per point of the sweep followed by reshape. It grows with n n n on every input except the spiral, where it stays near 22, and for n = 50000 n = 50000 n = 50000 it ranges from 23 on the spiral to 981 on the perturbed grid.
Figure 5. Means. Open (half-filled) markers: the reference is LB on all (some) instances.
Figure 6. Mean size divided by the reference, per input. Markers as in Figure 5 .
Figure 7. Sweep + reshape: mean number of dumbbells per point, per input.
Running times (Q2). Figure 8 reports the running times and the memory. On average, CK box and CK take 0.5 s for n = 10000 n = 10000 n = 10000 (at most 1.2 s) and 3.7 s and 4.1 s for n = 50000 n = 50000 n = 50000 , and the sweep takes 0.3 s for n = 1000 n = 1000 n = 1000 , 15 s for n = 10000 n = 10000 n = 10000 , and 5 min for n = 50000 n = 50000 n = 50000 . For n = 50000 n = 50000 n = 50000 ,
CK, the sweep, and reshape use up to 8, 15, and 22 GB. Computing OPT, including the enumeration of the maximal dumbbells, takes 0.07 s for n = 200 n = 200 n = 200 and 15 s for n = 1000 n = 1000 n = 1000 (median where CPLEX proves optimality). After the sweep, computing LB1 _1 1 takes on average 16 s for n = 10000 n = 10000 n = 10000 and 10 min for n = 50000 n = 50000 n = 50000 , and computing LB takes 2.7 min and 82 min (Figure 4 ).
Local search (Q3). We ran reshape (§ 3.2 ) from CK and from the sweep on every instance, for 100 s for n ≤ 1000 n \le1000 n ≤ 1000 , 1000 s for $2000 \le n \le 10000$, and 5000 s above. LNS ran with the same budgets, on every instance for n ≤ 1000 n \le1000 n ≤ 1000 and on samples of 3 instances for n = 10000 n = 10000 n = 10000 and $n = 50000 ({xref}Figure 9 and {xref}Table 2). Reshape ends at most as large as LNS from the same start on every instance, and smaller on average for every $n$. It reaches the final size of LNS within 1% of the budget, while LNS improves CK from 1.66 to 1.39 times the reference for $n = 10000$ and from 1.89 to 1.82 for $n = 50000$, where it tries only a small fraction of the dumbbells within its budget ({xref}Section 5.1). On the 164 instances with $n \le 1000$ where OPT is known, the sweep followed by reshape is on average 0.002% and at most 0.02% above OPT, and it reaches OPT on 101 of them (all 22 for $n = 200$, 13 of 22 for $n = 500$, and 1 of 13 for $n = 1000$), against 0.23%, 1.5%, and 18 for LNS from the sweep. It is on average at 1.05 LB for $n = 10000$ (at most 1.10 LB) and 1.11 LB for $n = 50000$ (at most 1.22 LB), against 1.22 LB and 1.38 LB for the sweep alone (right column of {xref}Figure 6). For the same total time, including the time to build the start and to set up reshape, the best results are obtained by CK followed by reshape ({xref}Figure 10`), although CK is on average larger than the output of the sweep. On every instance with n ≥ 20000 n \ge20000 n ≥ 20000 and on 378 of the 396 instances with n ≤ 10000 n \le10000 n ≤ 10000 , it is smaller than the output of the sweep before the sweep has finished; this takes on average 89% of the running time of the sweep for n = 10000 n = 10000 n = 10000 and 76% for n = 50000 n = 50000 n = 50000 . At every later time and on every instance, the sweep followed by reshape is at most 0.73% smaller, and never smaller for n ≥ 20000 n \ge20000 n ≥ 20000 . However, the approximation factor that we prove for CK followed by reshape is larger: since reshape never increases the size, it is 576 for ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 (§ 7 ), against 40 for the sweep followed by reshape (Theorem 7 ). For the same reshape time, the two starts end within 0.42% of each other for n ≤ 10000 n \le10000 n ≤ 10000 . For n ≥ 20000 n \ge20000 n ≥ 20000 , where reshape has not converged after 5000 s, the run from CK ends smaller on 39 of the 40 instances, by 0.4% on average for n = 50000 n = 50000 n = 50000 and by at most 1.2%. Since the two starts end close to each other, the sweep matters mainly for its lower bound and its
approximation factor when reshape follows.
Partition WSPDs (Q4). We convert a cover WSPD into a partition WSPD by processing its dumbbells one by one. For the current dumbbell { X , Y } \{X,Y\} { X , Y } , let U U U be the set of its pairs that no earlier dumbbell covers. Two points of X X X are grouped if they have the same partners in Y Y Y among the pairs of U U U , and each group X ′ ⊆ X X' \subseteq X X ′ ⊆ X with partners Y ′ ⊆ Y Y' \subseteq Y Y ′ ⊆ Y gives the dumbbell { X ′ , Y ′ } \{X',Y'\} { X ′ , Y ′ } . The same is done with the roles of X X X and Y Y Y exchanged, and the split into fewer dumbbells is kept. These dumbbells cover the pairs of U U U exactly once, and they are ε \varepsilon ε -separated by Observation 4 . The order comes from a priority queue that holds, for every dumbbell, the number of dumbbells into which its uncovered pairs split: the next dumbbell has the smallest number, ties broken by size, largest first. The numbers are updated lazily.
A final merge pass replaces two dumbbells { S , O 1 } \{S,O_1\} { S , O 1 } and { S , O 2 } \{S,O_2\} { S , O 2 } with a common side by { S , O 1 ∪ O 2 } \{S,O_1 \cup O_2\} { S , O 1 ∪ O 2 } if it is ε \varepsilon ε -separated. The result is still a partition WSPD. The pass tries at most 256 dumbbells per side and is repeated until no merge occurs, at most 20 times. It applies to every partition WSPD, also to CK and the quadtree.
The conversion has no size guarantee (Figure 11 and Table 4 ). For the sweep followed by reshape, the partition WSPD is on average 1.015, 1.13, and 1.18 times the reference for n = 1000 n = 1000 n = 1000 , 10000, and 20000 (at most 1.40, on the perturbed grid with n = 20000 n = 20000 n = 20000 ), against 1.003, 1.05, and 1.06 for the cover WSPD, and the conversion takes at most 54 s for n = 10000 n = 10000 n = 10000 and 142 s for n = 20000 n = 20000 n = 20000 . CK, which is a partition WSPD, is at 1.24, 1.55, and 1.66, and at 1.11, 1.46, and 1.59 after the merge pass. It is never smaller than the converted WSPD, also after the merge pass. Converting the optimal WSPDs with n = 500 n = 500 n = 500 gives partition WSPDs of size 1.004 OPTε _\varepsilon ε on average and at most 1.0125 OPTε _\varepsilon ε , which bounds the partition optimum on these instances. The quadtree construction of § 7 , with exact tests, is at 1.71, 2.45, and 2.78 times the reference, and at 1.15, 1.98, and 2.36 after the merge pass. Despite its smaller proven factor, it is larger than CK on average for every n n n , with or without merging.
Figure 11. Partition WSPDs: mean size / reference, (a, b) per input. Markers as in Figure 5.
Experiments in Three Dimensions
We ran the experiments of § 5.1 and § 5.2 on points in R 3 \mathbb{R}^{3} R 3 , with ε = 1 / 20 \varepsilon= 1/20 ε = 1/20 : the sweep, CK box, CK, reshape and LNS, the conversion into partition WSPDs, and the computations of OPT, LB, and α \alpha α . Table 5 gives the results per input for n ∈ { 1000 , 10000 } n \in\{1000, 10000\} n ∈ { 1000 , 10000 } .
Table 5 Size divided by the reference in R 3 \mathbb{R}^{3} R 3 , per input (one instance each). The column “Pairs” gives ( n 2 ) \binom{n}{2} ( 2 n ) divided by the reference. †: the reference is the lower bound. Bold: smallest construction of the row.
Table 5.
Implementation. The experiments in R 3 \mathbb{R}^{3} R 3 use a separate C++ implementation, with its own kd-tree. As in the plane, points have integer coordinates, all separation tests are exact, and every output is checked by a brute-force verifier for coverage and exact separation, and, for partition WSPDs, for covering every pair exactly once. The greedy sweep uses the grid pieces of § 4 : 64 cubes of side ε D / 2 \varepsilon D/2 ε D /2 in the ball and the 32 of them that meet the half-ball. A step falls back to the fixed collection only if it has fewer nonempty products than the dumbbells grown in the step, which happened in 117 steps over all instances, at most a fraction 10 − 5 10^{-5} 1 0 − 5 of the steps of any instance. CK splits the longest side of the bounding box of a node at its midpoint, and reshape and LNS relabel the points in Morton order. On planar instances embedded in the plane z = 0 z = 0 z = 0 , CK box and CK give exactly the sizes of the planar implementation, and the sweep is within 0.15% of it: ties are broken by the order in which the range queries report the points. The partition WSPDs are the conversion of Q4 with the merge pass, and the octree version of the quadtree construction of § 7 , with exact tests. OPT, LB (with 30 plateau passes), α \alpha α , and LNS are computed as in the plane (§ 3.3 and § 5.1 ). Reshape runs from CK and from the sweep on every instance, for 100 s for n ≤ 1000 n \le1000 n ≤ 1000 and 1000 s for larger n n n , and LNS from both starts, with the same budgets, on all instances with n = 200 n = 200 n = 200 , on all instances with n = 1000 n = 1000 n = 1000 , and on three instances with n = 10000 n = 10000 n = 10000 (uniform, clustered, and the bunny). All runs are single-threaded, with up to 11 runs in parallel, on the machine of § 5.1 ; the times of the sweep, of CK box, and of CK come from separate runs of each.
Inputs. The synthetic inputs (Figure 12 ) are generated in the cube [ 0 , M ] 3 [0,M]^{3} [ 0 , M ] 3 , with M = 10 6 M = 10^{6} M = 1 0 6 , and rounded to integer coordinates: uniform in the cube; Gaussian (around the center of the cube, standard deviation M / 8 M/8 M /8 in each coordinate); clustered (max { 2 , n / 20 } \max\{2,n/20\} max { 2 , n /20 } uniform centers, each point Gaussian around a random center with standard deviation M / 100 M/100 M /100 ); perturbed grid (a grid with ⌈ n 1 / 3 ⌉ \lceil n^{1/3}\rceil ⌈ n 1/3 ⌉ points per side, filled layer by layer, each point moved by a Gaussian of standard deviation 2% of the spacing); conical spiral (the point 2000 ( cos 3 t , sin 3 t , 1 ) 2000(\cos3t,\sin3t,1) 2000 ( cos 3 t , sin 3 t , 1 ) relative to the center of the cube, with t t t uniform in [ 0 , 6 ] [0,6] [ 0 , 6 ] ); and spherical shell (around the center of the cube, uniform direction, radius uniform in [ 1 , 1.1 ] ⋅ M / 4 [1,1.1]\cdot M/4 [ 1 , 1.1 ] ⋅ M /4 ). Duplicate points are discarded and replaced. The scans are four meshes of the Stanford 3D Scanning Repository [20 ] : the bunny, the armadillo, the XYZ RGB dragon, and the happy Buddha, with 35947, 49990, 125066, and 49251 vertices. Each is scaled so that the longest side of its bounding box is 10 6 10^{6} 1 0 6 and rounded, and we use a random sample of n n n vertices. We use the values of n n n of § 5.1 , up to 10000: from 200 to 1000 in steps of 100 and from 2000 to 10000 in steps of 1000. For each n n n , there is one instance per generator and one sample of each scan, so 10 instances, and 180 in all.
Figure 12. Synthetic instances and scans in R 3 \mathbb{R}^3 R 3 for n = 1000 n = 1000 n = 1000 .
Reference value. CPLEX proves optimality on all 90 instances with n ≤ 1000 n \le1000 n ≤ 1000 . Computing OPT takes a median of 3.2 s for n = 1000 n = 1000 n = 1000 , but up to 55 min on the conical spirals, where the enumeration of the maximal dumbbells dominates. For larger n n n , the reference is LB. Where OPT is known (Figure 13 ), LB is on average 0.999, 0.998, and 0.998 times OPT for n = 200 n = 200 n = 200 , 500, and 1000, at least 0.986 OPT on every instance, and equal to OPT on 20 instances. The number of steps L B 0 \mathrm{LB}_{0} LB 0 is on average 0.99, 0.98, and 0.97 times OPT, and at least 0.86 OPT.
Figure 13. The lower bounds in R 3 \mathbb{R}^3 R 3 : means over the instances.
For n ≤ 500 n \le500 n ≤ 500 , α \alpha α is at least 0.987 OPT and on average at least 0.998 OPT; CPLEX computes it in at most 88 s. Of the gap between L B 0 \mathrm{LB}_0 LB 0 and α \alpha α , the swaps close 85% and the plateau moves another 14%, and L B = α \mathrm{LB} = \alpha LB = α on 31 of these 40 instances. The ratio L B / L B 0 \mathrm{LB}/\mathrm{LB}_0 LB / LB 0 grows from 1.03 for n = 1000 n = 1000 n = 1000 to 1.09 for n = 10000 n = 10000 n = 10000 .
Quality. Figure 14 summarizes the results, and Figure 15 shows them per input. The sweep is never larger than CK and CK box. It is smaller than both on every instance except the perturbed grids with n ≤ 1000 n \le1000 n ≤ 1000 , where every dumbbell of every WSPD is a single pair, so that all methods output ( n 2 ) \binom{n}{2} ( 2 n ) dumbbells. For n = 500 n = 500 n = 500 , the sweep is on average 1.4% above OPT (at most 9%), and CK box and CK are 15% and 12% above (at most 63% and 36%). For n = 1000 n = 1000 n = 1000 , the sweep is at 1.02 OPT and CK at 1.18 OPT. For n = 10000 n = 10000 n = 10000 , the sweep is on average at 1.13 LB (at most 1.23 LB), and CK box and CK at 1.61 LB and 1.49 LB (at most 2.03 LB and 1.68 LB). Figure 16 gives the number of dumbbells per point of the sweep followed by reshape and the number of pairs per dumbbell of the reference, ( n 2 ) \binom{n}{2} ( 2 n ) divided by the reference. For n ≤ 1000 n \le1000 n ≤ 1000 , the uniform, Gaussian, and perturbed grid inputs have at most 1.16 pairs per dumbbell, so almost all dumbbells are single pairs and every method is close to OPT. For n = 10000 n = 10000 n = 10000 , the number of pairs per dumbbell ranges from 1.16 on the perturbed grid to 244 on the conical spiral, and it is between 7.6 and 9.0 on the scans; the number of dumbbells per point ranges from 21 on the conical spiral to 4348 on the perturbed grid.
Figure 14. Means in R 3 \mathbb{R}^{3} R 3 . Open markers: the reference is LB on all instances.
Figure 15. Size divided by the reference in R 3 \mathbb{R}^{3} R 3 , per input. Markers as in Figure 14 .
Figure 16. Sweep + reshape in R 3 \mathbb{R}^3 R 3 : (a) dumbbells per point, (b) pairs per dumbbell of the reference, per input.
Running times. Figure 17 reports the running times and the memory. On average, the sweep takes 0.5 s for n = 1000 n = 1000 n = 1000 and 45 s for n = 10000 n = 10000 n = 10000 , and CK box and CK take 1.4 s and 1.5 s for n = 10000 n = 10000 n = 10000 . The sweep followed by reshape reaches 1.001 OPT in 1.0 s on average for n = 1000 n = 1000 n = 1000 . After the sweep, computing L B 1 \mathrm{LB}_{1} LB 1 takes 26 s and computing LB 3.9 min on average for n = 10000 n = 10000 n = 10000 . For n = 10000 n = 10000 n = 10000 , the sweep and reshape use up to 8.4 GB and CK up to 5.0 GB, on the perturbed grid, whose WSPDs have the most dumbbells.
Figure 17. Mean running time and largest peak memory in R 3 \mathbb{R}^3 R 3 .
Local search. Reshape, from either start, is at most 0.03% above OPT on the 90 instances where OPT is known, and reaches OPT on 72 of them from CK and on 69 from the sweep. For n = 10000 n = 10000 n = 10000 , it is on average at 1.021 LB and at most 1.043 LB, against 1.13 LB for the sweep alone. The two starts end within 0.03% of each other on every instance. Reshape ends at most as large as LNS from the same start in every run of Figure 18 . For n = 1000 n = 1000 n = 1000 , LNS ends on average 0.36% above the reference from CK and 0.19% from the sweep, against less than 0.01% for reshape, and for n = 10000 n = 10000 n = 10000 , LNS improves CK from 1.55 to 1.34 times the reference and the sweep from 1.15 to 1.10 (means over the three instances), against 1.02 for reshape from both starts. Figure 19 shows reshape from both starts against the total time, including the time to build the start.
Figure 18. Local search in R 3 \mathbb{R}^{3} R 3 : mean size / reference over time, on all instances for n ∈ { 200 , 1000 } n \in\{200, 1000\} n ∈ { 200 , 1000 } .
Figure 19. Mean size / reference in R 3 \mathbb{R}^{3} R 3 per input over the total time: build of the start, then reshape.
Partition WSPDs. Figure 20 shows the partition WSPDs. For the sweep followed by reshape, the converted partition WSPD is on average 1.005 and 1.055 times the reference for n = 1000 n = 1000 n = 1000 and 10000, against 1.000 and 1.021 for the cover WSPD. CK is at 1.18 and 1.49, and at 1.09 and 1.46 after the merge pass. It is never smaller than the converted WSPD, also after the merge pass. The octree construction is at 1.51 and 2.44, and at 1.14 and 2.25 after the merge pass; with the merge pass, it is smaller than CK with the merge pass on 5 instances, all with n ≤ 300 n \le300 n ≤ 300 .
Figure 20. Partition WSPDs in R 3 \mathbb{R}^{3} R 3 : mean size / reference, (a, b) per input. Markers as in Figure 14.
Larger ε \varepsilon ε
For ε > 1 / 16 \varepsilon> 1/16 ε > 1/16 , the pieces of Section 2 may give dumbbells that are not ε \varepsilon ε -separated: the proof of Theorem 3 bounds the distance between two pieces only by ( 1 − 2 ε ) D (1-2\varepsilon)D ( 1 − 2 ε ) D , which is useless for ε ≥ 1 / 2 \varepsilon\ge1/2 ε ≥ 1/2 . We show that pieces that depend on ε \varepsilon ε , together with a separation test, give both sweeps a constant factor for every ε > 0 \varepsilon> 0 ε > 0 . The new ingredient is a lower bound on the distance between two pieces that uses a dumbbell covering the anchor. Throughout, P ⊂ R 2 P \subset\mathbb{R}^{2} P ⊂ R 2 .
Piece families. Let H = { z ∈ B ( 0 , 1 ) : z 1 ≥ 0 } H = \{z \in\mathbb{B}(0,1) : z_{1} \ge0\} H = { z ∈ B ( 0 , 1 ) : z 1 ≥ 0 } be the unit half-disk, where z 1 z_{1} z 1 denotes the first coordinate of z z z . A piece family L = ( L + , L ∘ ) \mathcal{L} = (\mathcal{L}^{+},\mathcal{L}^{\circ}) L = ( L + , L ∘ ) consists of a partition L + \mathcal{L}^{+} L + of H H H and a partition L ∘ \mathcal{L}^{\circ} L ∘ of B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) into finitely many pieces. Each piece Π \Pi Π comes with numbers 0 ≤ a Π ≤ b Π ≤ 1 0 \le a_{\Pi} \le b_{\Pi} \le1 0 ≤ a Π ≤ b Π ≤ 1 and β Π > 0 \beta_{\Pi} > 0 β Π > 0 such that a Π ≤ ∥ z ∥ ≤ b Π a_{\Pi} \le\lVert z\rVert\le b_{\Pi} a Π ≤ ∥ z ∥ ≤ b Π for every z ∈ Π z \in\Pi z ∈ Π and diam ( Π ) ≤ β Π \operatorname{diam}(\Pi) \le\beta_{\Pi} diam ( Π ) ≤ β Π . The size of L \mathcal{L} L is ∣ L + ∣ ⋅ ∣ L ∘ ∣ |\mathcal{L}^{+}| \cdot|\mathcal{L}^{\circ}| ∣ L + ∣ ⋅ ∣ L ∘ ∣ . For 0 ≤ a ≤ b ≤ 1 0 \le a \le b \le1 0 ≤ a ≤ b ≤ 1 and 0 ≤ c ≤ d ≤ 1 0 \le c \le d \le1 0 ≤ c ≤ d ≤ 1 , let
M ε ( a , b ; c , d ) = min r ∈ [ a , b ] , s ∈ [ c , d ] max { 1 − ε ( r + s ) , r , s , 1 1 + 2 ε } . M_{\varepsilon}(a,b;c,d) = \min_{\substack{r \in[a,b],\,s \in[c,d]}} \max\left\{1-\varepsilon(r+s),\,r,\,s,\,\frac{1}{1+2\varepsilon}\right\}. M ε ( a , b ; c , d ) = r ∈ [ a , b ] , s ∈ [ c , d ] min max { 1 − ε ( r + s ) , r , s , 1 + 2 ε 1 } .
The family is ε \varepsilon ε -admissible if all Π ∈ L + \Pi\in\mathcal{L}^{+} Π ∈ L + and Σ ∈ L ∘ \Sigma\in\mathcal{L}^{\circ} Σ ∈ L ∘ satisfy
max { β Π , β Σ } ≤ max { 1 − ε ( b Π + b Σ ) , M ε ( a Π , b Π ; a Σ , b Σ ) − ε ( β Π + β Σ ) } . (1) \max\{\beta_{\Pi},\beta_{\Sigma}\} \le\max\left\{1-\varepsilon(b_{\Pi}+b_{\Sigma}),\,M_{\varepsilon}(a_{\Pi},b_{\Pi};a_{\Sigma},b_{\Sigma})-\varepsilon(\beta_{\Pi}+\beta_{\Sigma})\right\}. \tag*{(1)} max { β Π , β Σ } ≤ max { 1 − ε ( b Π + b Σ ) , M ε ( a Π , b Π ; a Σ , b Σ ) − ε ( β Π + β Σ ) } . (1)
Every term on the right-hand side is nonincreasing in ε \varepsilon ε , so a family that is ε 0 \varepsilon_{0} ε 0 -admissible is ε \varepsilon ε -admissible for every ε ≤ ε 0 \varepsilon\le\varepsilon_{0} ε ≤ ε 0 . The first term is the bound used in the proof of Theorem 3: the pieces of Section 2, scaled to radius 1, with a Π = 0 a_{\Pi}=0 a Π = 0 , b Π = 1 b_{\Pi}=1 b Π = 1 , and the diameters of Lemma 1, form a 1 / 16 1/16 1/16 -admissible family of size 40.
The collection of a family. Fix a piece family L \mathcal{L} L . For a step with anchor { p , q } \{p,q\} { p , q } , where p ≺ q p \prec q p ≺ q and D = ∥ p q ∥ D=\lVert pq\rVert D = ∥ pq ∥ , let A Π = { z ∈ P : z ⪰ p , z ∈ p + ε D Π } A_{\Pi}=\{z \in P : z \succeq p,\ z \in p+\varepsilon D\Pi\} A Π = { z ∈ P : z ⪰ p , z ∈ p + ε D Π } for Π ∈ L + \Pi\in\mathcal{L}^{+} Π ∈ L + , and let C Σ = P ∩ ( q + ε D Σ ) C_{\Sigma}=P \cap(q+\varepsilon D\Sigma) C Σ = P ∩ ( q + ε D Σ ) for Σ ∈ L ∘ \Sigma\in\mathcal{L}^{\circ} Σ ∈ L ∘ . The L \mathcal{L} L -collection of the step consists of the dumbbells { A Π , C Σ } \{A_{\Pi},C_{\Sigma}\} { A Π , C Σ } whose sides are nonempty and disjoint and that are ε \varepsilon ε -separated. Both conditions are tested on the points, so the L \mathcal{L} L -collection consists of at most ∣ L + ∣ ⋅ ∣ L ∘ ∣ |\mathcal{L}^{+}|\cdot|\mathcal{L}^{\circ}| ∣ L + ∣ ⋅ ∣ L ∘ ∣ dumbbells, all ε \varepsilon ε -separated. For the pieces of Section 2 and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , every dumbbell { A i , C k } \{A_{i},C_{k}\} { A i , C k } with nonempty sides passes both tests, so the L \mathcal{L} L -collection is the fixed collection.
Lemma 13 (Piece separation). Let p , q ∈ R 2 p,q \in\mathbb{R}^{2} p , q ∈ R 2 , D = ∥ p q ∥ D=\lVert pq\rVert D = ∥ pq ∥ , and let { X , Y } \{X,Y\} { X , Y } be an ε \varepsilon ε -separated dumbbell with p , x ∈ X p,x \in X p , x ∈ X and q , y ∈ Y q,y \in Y q , y ∈ Y . Let A ∋ x A \ni x A ∋ x and C ∋ y C \ni y C ∋ y be sets such that a ε D ≤ ∥ p z ∥ ≤ b ε D a\varepsilon D \le\lVert pz\rVert\le b\varepsilon D a ε D ≤ ∥ p z ∥ ≤ b ε D for every z ∈ A z \in A z ∈ A , c ε D ≤ ∥ q z ∥ ≤ d ε D c\varepsilon D \le\lVert qz\rVert\le d\varepsilon D c ε D ≤ ∥ q z ∥ ≤ d ε D for every z ∈ C z \in C z ∈ C , diam ( A ) ≤ β ε D \operatorname{diam}(A) \le\beta\varepsilon D diam ( A ) ≤ β ε D , and diam ( C ) ≤ β ′ ε D \operatorname{diam}(C) \le\beta'\varepsilon D diam ( C ) ≤ β ′ ε D . Then
dist ( A , C ) ≥ D ⋅ max { 1 − ε ( b + d ) , M ε ( a , b ; c , d ) − ε ( β + β ′ ) } . \operatorname{dist}(A,C) \ge D \cdot\max\left\{1-\varepsilon(b+d),\,M_{\varepsilon}(a,b;c,d)-\varepsilon(\beta+\beta')\right\}. dist ( A , C ) ≥ D ⋅ max { 1 − ε ( b + d ) , M ε ( a , b ; c , d ) − ε ( β + β ′ ) } .
Proof. Let a ′ ∈ A a' \in A a ′ ∈ A and c ′ ∈ C c' \in C c ′ ∈ C . First, ∥ a ′ c ′ ∥ ≥ ∥ p q ∥ − ∥ p a ′ ∥ − ∥ q c ′ ∥ ≥ ( 1 − ε ( b + d ) ) D \lVert a'c'\rVert\ge\lVert pq\rVert-\lVert pa'\rVert-\lVert qc'\rVert\ge(1-\varepsilon(b+d))D ∥ a ′ c ′ ∥ ≥ ∥ pq ∥ − ∥ p a ′ ∥ − ∥ q c ′ ∥ ≥ ( 1 − ε ( b + d )) D . Second, let ℓ = dist ( X , Y ) \ell=\operatorname{dist}(X,Y) ℓ = dist ( X , Y ) , r = ∥ p x ∥ / ( ε D ) r=\lVert px\rVert/(\varepsilon D) r = ∥ p x ∥ / ( ε D ) , and s = ∥ q y ∥ / ( ε D ) s=\lVert qy\rVert/(\varepsilon D) s = ∥ q y ∥ / ( ε D ) , so that r ∈ [ a , b ] r \in[a,b] r ∈ [ a , b ] and s ∈ [ c , d ] s \in[c,d] s ∈ [ c , d ] . Since { X , Y } \{X,Y\} { X , Y } is ε \varepsilon ε -separated, ℓ ≥ diam ( X ) / ε ≥ ∥ p x ∥ / ε = r D \ell\ge\operatorname{diam}(X)/\varepsilon\ge\lVert px\rVert/\varepsilon=rD ℓ ≥ diam ( X ) / ε ≥ ∥ p x ∥ / ε = r D , and similarly ℓ ≥ s D \ell\ge sD ℓ ≥ sD . By Observation 2, ℓ ≥ D / ( 1 + 2 ε ) \ell\ge D/(1+2\varepsilon) ℓ ≥ D / ( 1 + 2 ε ) . Moreover, ∥ x y ∥ ≥ ℓ \lVert xy\rVert\ge\ell ∥ x y ∥ ≥ ℓ and ∥ x y ∥ ≥ ∥ p q ∥ − ∥ p x ∥ − ∥ q y ∥ = ( 1 − ε ( r + s ) ) D \lVert xy\rVert\ge\lVert pq\rVert-\lVert px\rVert-\lVert qy\rVert=(1-\varepsilon(r+s))D ∥ x y ∥ ≥ ∥ pq ∥ − ∥ p x ∥ − ∥ q y ∥ = ( 1 − ε ( r + s )) D . Hence ∥ x y ∥ ≥ M ε ( a , b ; c , d ) D \lVert xy\rVert\ge M_{\varepsilon}(a,b;c,d)D ∥ x y ∥ ≥ M ε ( a , b ; c , d ) D , and ∥ a ′ c ′ ∥ ≥ ∥ x y ∥ − diam ( A ) − diam ( C ) ≥ ( M ε ( a , b ; c , d ) − ε ( β + β ′ ) ) D \lVert a'c'\rVert\ge\lVert xy\rVert-\operatorname{diam}(A)-\operatorname{diam}(C) \ge(M_{\varepsilon}(a,b;c,d)-\varepsilon(\beta+\beta'))D ∥ a ′ c ′ ∥ ≥ ∥ x y ∥ − diam ( A ) − diam ( C ) ≥ ( M ε ( a , b ; c , d ) − ε ( β + β ′ )) D .
Lemma 14. If L \mathcal{L} L is ε \varepsilon ε -admissible, then, in every step, with anchor { p , q } \{p,q\} { p , q } , the L \mathcal{L} L -collection covers R p q R_{pq} R pq .
Proof. Let { x , y } ∈ R p q \{x,y\}\in R_{pq} { x , y } ∈ R pq . By Observation 4, we may name x x x and y y y so that { { p , x } , { q , y } } \{\{p,x\},\{q,y\}\} {{ p , x } , { q , y }} has disjoint sides and is ε \varepsilon ε -separated. Its distance is at most D D D , so ∥ p x ∥ ≤ ε D \lVert px\rVert\leq\varepsilon D ∥ p x ∥ ≤ ε D and ∥ q y ∥ ≤ ε D \lVert qy\rVert\leq\varepsilon D ∥ q y ∥ ≤ ε D . Since x ⪰ p x\succeq p x ⪰ p by the definition of R p q R_{pq} R pq , the first coordinate of x x x is at least that of p p p , so x ∈ p + ε D H x\in p+\varepsilon D H x ∈ p + ε D H . Hence x ∈ A Π x\in A_{\Pi} x ∈ A Π for some Π ∈ L + \Pi\in\mathcal{L}^{+} Π ∈ L + , and similarly y ∈ C Σ y\in C_{\Sigma} y ∈ C Σ for some Σ ∈ L ∘ \Sigma\in\mathcal{L}^{\circ} Σ ∈ L ∘ . By the definition of a piece family, A = A Π A=A_{\Pi} A = A Π and C = C Σ C=C_{\Sigma} C = C Σ satisfy the conditions of Lemma 13 with ( a , b , β ) = ( a Π , b Π , β Π ) (a,b,\beta)=(a_{\Pi},b_{\Pi},\beta_{\Pi}) ( a , b , β ) = ( a Π , b Π , β Π ) and ( c , d , β ′ ) = ( a Σ , b Σ , β Σ ) (c,d,\beta')=(a_{\Sigma},b_{\Sigma},\beta_{\Sigma}) ( c , d , β ′ ) = ( a Σ , b Σ , β Σ ) . By Lemma 13 and (1),
dist ( A Π , C Σ ) ≥ D max { β Π , β Σ } ≥ max { diam ( A Π ) , diam ( C Σ ) } / ε . \operatorname{dist}(A_{\Pi},C_{\Sigma})\geq D\max\{\beta_{\Pi},\beta_{\Sigma}\}\geq\max\{\operatorname{diam}(A_{\Pi}),\operatorname{diam}(C_{\Sigma})\}/\varepsilon. dist ( A Π , C Σ ) ≥ D max { β Π , β Σ } ≥ max { diam ( A Π ) , diam ( C Σ )} / ε .
The left-hand side is positive, so the sides are disjoint, and the dumbbell { A Π , C Σ } \{A_{\Pi},C_{\Sigma}\} { A Π , C Σ } is ε \varepsilon ε -separated. Hence it belongs to the L \mathcal{L} L -collection, and it covers { x , y } \{x,y\} { x , y } .
The sweeps. Let L \mathcal{L} L be a piece family of size c c c . The sweep with L \mathcal{L} L outputs the L \mathcal{L} L -collection in every step. In every step, the greedy sweep with L \mathcal{L} L computes a greedy cover of R p q R_{pq} R pq as in § 3.1 , except that, if ∣ R p q ∣ > 16 \lvert R_{pq}\rvert>16 ∣ R pq ∣ > 16 , it stops after c c c grown dumbbells. It outputs the greedy cover if the greedy cover covers R p q R_{pq} R pq and has at most as many dumbbells as the L \mathcal{L} L -collection, and it outputs the L \mathcal{L} L -collection otherwise. For the pieces of § 2 and ε ≤ 1 / 16 \varepsilon\leq1/16 ε ≤ 1/16 , these are the fixed sweep of § 2 and the greedy sweep of § 3.1 . As in § 3.1 , the cap does not change the output: if ∣ R p q ∣ > 16 \lvert R_{pq}\rvert>16 ∣ R pq ∣ > 16 , every grown dumbbell belongs to the greedy cover, so a greedy cover with more than c c c dumbbells is larger than the L \mathcal{L} L -collection.
Theorem 15. Let ε > 0 \varepsilon>0 ε > 0 , let L \mathcal{L} L be an ε \varepsilon ε -admissible piece family of size c c c , and let P ⊂ R 2 P\subset\mathbb{R}^{2} P ⊂ R 2 . The sweep and the greedy sweep with L \mathcal{L} L perform at most OPT ε \operatorname{OPT}_{\varepsilon} OPT ε steps and output an ε \varepsilon ε -WSPD of size at most c OPT ε c\operatorname{OPT}_{\varepsilon} c OPT ε . For a fixed family and ε ≥ 1 / 16 \varepsilon\geq1/16 ε ≥ 1/16 , both run in O ( n 3 ) O(n^{3}) O ( n 3 ) time and O ( n 2 ) O(n^{2}) O ( n 2 ) space.
Proof. Size and steps. Every output dumbbell is ε \varepsilon ε -separated: the grown dumbbells by construction, and those of the L \mathcal{L} L -collection by its tests. By Lemma 14, every step, with anchor { p , q } \{p,q\} { p , q } , covers R p q R_{pq} R pq , which contains { p , q } \{p,q\} { p , q } , with at most c c c dumbbells. As explained before Theorem 7 , the proofs of validity and of the approximation factor in Theorem 3 use only this property, with c c c in place of 40, and Observation 5 bounds the number of steps by OPT ε \operatorname{OPT}_{\varepsilon} OPT ε .
Running time. Let ε ≥ 1 / 16 \varepsilon\geq1/16 ε ≥ 1/16 . Every 1 / 16 1/16 1/16 -separated dumbbell is ε \varepsilon ε -separated, so OPT ε ≤ OPT 1 / 16 = O ( n ) \operatorname{OPT}_{\varepsilon}\leq\operatorname{OPT}_{1/16}=O(n) OPT ε ≤ OPT 1/16 = O ( n ) by the CK construction [7 ] , and there are O ( n ) O(n) O ( n ) steps. We store the covered pairs in an n × n n\times n n × n table and inspect every pair once, as in the proof of Theorem 3 . It remains to show that a step takes O ( n 2 ) O(n^{2}) O ( n 2 ) time. Every point is assigned to its piece in O ( 1 ) O(1) O ( 1 ) time, since the family is fixed. The diameters of all sets A Π A_{\Pi} A Π and C Σ C_{\Sigma} C Σ are computed in O ( n 2 ) O(n^{2}) O ( n 2 ) time. Testing the dumbbell { A Π , C Σ } \{A_{\Pi},C_{\Sigma}\} { A Π , C Σ } takes O ( ∣ A Π ∣ ⋅ ∣ C Σ ∣ ) O(\lvert A_{\Pi}\rvert\cdot\lvert C_{\Sigma}\rvert) O (∣ A Π ∣ ⋅ ∣ C Σ ∣) time, which sums to O ( n 2 ) O(n^{2}) O ( n 2 ) over all Π \Pi Π and Σ \Sigma Σ . Enumerating R p q R_{pq} R pq takes O ( n 2 ) O(n^{2}) O ( n 2 ) time, since compatibility is tested in O ( 1 ) O(1) O ( 1 ) time by Observation 4. A dumbbell is grown in O ( n 2 ) O(n^{2}) O ( n 2 ) time, as in the proof of Theorem 7 , and at most max { c , 16 } \max\{c,16\} max { c , 16 } dumbbells are grown. Marking the pairs covered by each of the at most c c c output dumbbells takes O ( n 2 ) O(n^{2}) O ( n 2 ) time. Hence the total time is O ( n 3 ) O(n^{3}) O ( n 3 ) , and the table takes O ( n 2 ) O(n^{2}) O ( n 2 ) space.
In particular, the number of steps of either sweep is a lower bound on OPT ε \operatorname{OPT}_{\varepsilon} OPT ε for every ε > 0 \varepsilon>0 ε > 0 .
Ring families. Radii 0 = r 0 < r 1 < ⋯ < r K = 1 0=r_{0}<r_{1}<\cdots<r_{K}=1 0 = r 0 < r 1 < ⋯ < r K = 1 and positive integers n 1 , … , n K n_{1},\ldots,n_{K} n 1 , … , n K define a partition of H H H : for j = 1 , … , K j=1,\ldots,K j = 1 , … , K , the j j j th ring, the set of points z ∈ H z\in H z ∈ H with r j − 1 ≤ ∥ z ∥ ≤ r j r_{j-1}\leq\lVert z\rVert\leq r_{j} r j − 1 ≤ ∥ z ∥ ≤ r j , is cut into n j n_{j} n j annular sectors of angle π / n j \pi/n_{j} π / n j . Similarly, other radii and integers define a partition of B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) , with sectors of angle 2 π / n j 2\pi/n_j 2 π / n j . These pieces form a ring family , in which a piece of the j j j th ring has a = r j − 1 a=r_{j-1} a = r j − 1 and b = r j b=r_j b = r j , and β \beta β is its diameter, given by the next lemma. As in Section 2, points on the boundary between two pieces are assigned to one of them arbitrarily. The pieces of Section 2 form a ring family with K = 2 K=2 K = 2 . Figure 21 shows the first four families of Table 6.
Figure 21. The ring families of Table 6 for ε 0 = 1 / 10 \varepsilon_0=1/10 ε 0 = 1/10 , 1 / 8 1/8 1/8 , 3 / 16 3/16 3/16 , and 1 / 4 1/4 1/4 : the pieces of the half-disk H H H (left) and of the disk B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) (right), and the size ∣ L + ∣ ⋅ ∣ L ∘ ∣ |\mathcal{L}^{+}|\cdot|\mathcal{L}^{\circ}| ∣ L + ∣ ⋅ ∣ L ∘ ∣ of the family.
Lemma 16. Let 0 ≤ a < b 0\le a<b 0 ≤ a < b and 0 < φ ≤ π 0<\varphi\le\pi 0 < φ ≤ π . The annular sector with radii a a a and b b b and angle φ \varphi φ (a circular sector if a = 0 a=0 a = 0 ) has diameter max { 2 b sin ( φ / 2 ) , a 2 + b 2 − 2 a b cos φ } \max\{2b\sin(\varphi/2),\sqrt{a^2+b^2-2ab\cos\varphi}\} max { 2 b sin ( φ /2 ) , a 2 + b 2 − 2 ab cos φ } .
Proof. Since φ ≤ π \varphi\le\pi φ ≤ π , the convex hull of the sector is bounded by the outer arc, the two radial segments, and the segment between the two inner corners (these corners coincide if a = 0 a=0 a = 0 ). Hence its extreme points are the points of the outer arc and the inner corners, and the diameter is attained by two of them. Two points of the outer arc are at distance at most 2 b sin ( φ / 2 ) 2b\sin(\varphi/2) 2 b sin ( φ /2 ) , with equality for the two outer corners. An inner corner and a point of the outer arc at angle θ ∈ [ 0 , φ ] \theta\in[0,\varphi] θ ∈ [ 0 , φ ] from it are at distance a 2 + b 2 − 2 a b cos θ \sqrt{a^2+b^2-2ab\cos\theta} a 2 + b 2 − 2 ab cos θ , which increases with θ \theta θ and is largest for the opposite outer corner. The two inner corners are at distance 2 a sin ( φ / 2 ) ≤ 2 b sin ( φ / 2 ) 2a\sin(\varphi/2)\le2b\sin(\varphi/2) 2 a sin ( φ /2 ) ≤ 2 b sin ( φ /2 ) .
A central piece of the disk with n 1 = 1 n_1=1 n 1 = 1 is a disk of diameter 2 r 1 2r_1 2 r 1 . Every other piece of a ring family has angle at most π \pi π .
Proposition 17. For each ε 0 \varepsilon_0 ε 0 in Table 6 , the ring family given there is ε 0 \varepsilon_0 ε 0 -admissible. Hence, for every ε ≤ ε 0 \varepsilon\le\varepsilon_0 ε ≤ ε 0 , the sweep and the greedy sweep with this family output an ε \varepsilon ε -WSPD of size at most c ( ε 0 ) OPT ε c(\varepsilon_0)\operatorname{OPT}_{\varepsilon} c ( ε 0 ) OPT ε , where c ( ε 0 ) c(\varepsilon_0) c ( ε 0 ) is its size.
Table 6. Table 6 Ring families that are ϵ 0 \epsilon_0 ϵ 0 -admissible, and their sizes c ( ϵ 0 ) c(\epsilon_0) c ( ϵ 0 ) . For each ϵ 0 \epsilon_0 ϵ 0 , the two rows give the rings of the half-disk H H H and of the disk B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) : the outer radius of each ring, in units of 1 / 240 1/240 1/240 , and its number of pieces. For ϵ ≤ 1 / 16 \epsilon\le1/16 ϵ ≤ 1/16 , the pieces of Section 2 give c = 40 c = 40 c = 40 .
Proof. In a ring family, a a a , b b b , and β \beta β depend only on the ring of a piece, so (1) has to be checked only for every pair of rings, one of H H H and one of B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) . The function minimized in the definition of M ε M_{\varepsilon} M ε is the maximum of four affine functions of ( r , s ) (r,s) ( r , s ) . Hence its minimum over the rectangle [ a , b ] × [ c , d ] [a,b]\times[c,d] [ a , b ] × [ c , d ] is attained at a corner, at a point of an edge where two of the four functions are equal, or at a point where three of them are equal, and M ε M_{\varepsilon} M ε is computed exactly by evaluating these finitely many candidates. We checked (1) at ε = ε 0 \varepsilon=\varepsilon_0 ε = ε 0 by computer, in floating-point arithmetic, for all pairs of rings of the ten families. The smallest slack is 2 ⋅ 10 − 5 2\cdot10^{-5} 2 ⋅ 1 0 − 5 , far above the rounding errors. The second part follows from Theorem 15 .
Corollary 18. Let ε > 0 \varepsilon>0 ε > 0 and β = max { 1 − 2 ε , ( 1 + 2 ε ) − 2 } \beta=\max\{1-2\varepsilon,(1+2\varepsilon)^{-2}\} β = max { 1 − 2 ε , ( 1 + 2 ε ) − 2 } . Some ε \varepsilon ε -admissible piece family has size at most 4 π 2 ( 1 + 1 / β ) 4 4\pi^2(1+1/\beta)^4 4 π 2 ( 1 + 1/ β ) 4 , which is less than 4 ⋅ 10 5 max { 1 , ε 8 } 4\cdot10^5\max\{1,\varepsilon^8\} 4 ⋅ 1 0 5 max { 1 , ε 8 } . Hence the sweep and the greedy sweep with this family output an ε \varepsilon ε -WSPD of size at most 4 ⋅ 10 5 max { 1 , ε 8 } OPT ε 4\cdot10^5\max\{1,\varepsilon^8\}\operatorname{OPT}_{\varepsilon} 4 ⋅ 1 0 5 max { 1 , ε 8 } OPT ε .
Proof. Let the pieces be the nonempty intersections of H H H , and of B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) , with the half-open squares of a grid of side β / 2 \beta/\sqrt{2} β / 2 , with a Π = 0 a_{\Pi}=0 a Π = 0 , b Π = 1 b_{\Pi}=1 b Π = 1 , and β Π = β \beta_{\Pi}=\beta β Π = β for every piece Π \Pi Π . If β = 1 − 2 ϵ \beta= 1 - 2\epsilon β = 1 − 2 ϵ , then the first term of (1) equals β \beta β . Otherwise, β = ( 1 + 2 ϵ ) − 2 \beta= (1 + 2\epsilon)^{-2} β = ( 1 + 2 ϵ ) − 2 , and since M ϵ ≥ 1 / ( 1 + 2 ϵ ) M_\epsilon\ge1/(1 + 2\epsilon) M ϵ ≥ 1/ ( 1 + 2 ϵ ) , the second term is at least 1 / ( 1 + 2 ϵ ) − 2 ϵ / ( 1 + 2 ϵ ) 2 = ( 1 + 2 ϵ ) − 2 = β 1/(1 + 2\epsilon) - 2\epsilon/(1 + 2\epsilon)^2 = (1 + 2\epsilon)^{-2} = \beta 1/ ( 1 + 2 ϵ ) − 2 ϵ / ( 1 + 2 ϵ ) 2 = ( 1 + 2 ϵ ) − 2 = β . Hence the family is ϵ \epsilon ϵ -admissible. A square that meets B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) lies in B ( 0 , 1 + β ) \mathbb{B}(0,1 + \beta) B ( 0 , 1 + β ) , since its diameter is β \beta β . Comparing areas, at most π ( 1 + β ) 2 / ( β 2 / 2 ) = 2 π ( 1 + 1 / β ) 2 \pi(1 + \beta)^2/(\beta^2/2) = 2\pi(1 + 1/\beta)^2 π ( 1 + β ) 2 / ( β 2 /2 ) = 2 π ( 1 + 1/ β ) 2 squares meet B ( 0 , 1 ) \mathbb{B}(0,1) B ( 0 , 1 ) , and hence H H H , so the family has size at most 4 π 2 ( 1 + 1 / β ) 4 4\pi^2(1 + 1/\beta)^4 4 π 2 ( 1 + 1/ β ) 4 . If ϵ ≤ 1 \epsilon\le1 ϵ ≤ 1 , then β ≥ 1 / 9 \beta\ge1/9 β ≥ 1/9 and 4 π 2 ( 1 + 1 / β ) 4 ≤ 4 π 2 ⋅ 10 4 < 4 ⋅ 10 5 4\pi^2(1 + 1/\beta)^4 \le4\pi^2 \cdot10^4 < 4 \cdot10^5 4 π 2 ( 1 + 1/ β ) 4 ≤ 4 π 2 ⋅ 1 0 4 < 4 ⋅ 1 0 5 . If ϵ ≥ 1 \epsilon\ge1 ϵ ≥ 1 , then 1 + 1 / β = 1 + ( 1 + 2 ϵ ) 2 ≤ 10 ϵ 2 1 + 1/\beta= 1 + (1 + 2\epsilon)^2 \le10\epsilon^2 1 + 1/ β = 1 + ( 1 + 2 ϵ ) 2 ≤ 10 ϵ 2 , and the size is less than 4 ⋅ 10 5 ϵ 8 4 \cdot10^5\epsilon^8 4 ⋅ 1 0 5 ϵ 8 .
Quadtree and Fair Split Tree Partition WSPD Constructions
We first prove Theorem 19 , on a quadtree construction, and then bound the size of the CK construction on a fair split tree by the same charging (Theorem 20 ).
The running times of this section are for dumbbells given as pairs of nodes of a tree, as in [7 ] . Listing the points of every dumbbell may take Ω ( n 2 ) \Omega(n^2) Ω ( n 2 ) time even if O P T ϵ = n − 1 \mathrm{OPT}_\epsilon= n - 1 OPT ϵ = n − 1 . Consider the points p i = ( i , ( 4 / ϵ ) i ) p_i = (i,(4/\epsilon)^i) p i = ( i , ( 4/ ϵ ) i ) of Section 1, and let p j p_j p j be the point of largest index in an ϵ \epsilon ϵ -separated dumbbell. If the side of p j p_j p j contained another point p l p_l p l , its diameter would be at least ( 1 − ϵ / 4 ) ( 4 / ϵ ) j (1-\epsilon/4)(4/\epsilon)^j ( 1 − ϵ /4 ) ( 4/ ϵ ) j , while its distance to a point p i p_i p i of the other side is at most ∥ p i p l ∥ ≤ 2 ( 4 / ϵ ) j − 1 = ( ϵ / 2 ) ( 4 / ϵ ) j \lVert p_i p_l\rVert\le2(4/\epsilon)^{j-1} = (\epsilon/2)(4/\epsilon)^j ∥ p i p l ∥ ≤ 2 ( 4/ ϵ ) j − 1 = ( ϵ /2 ) ( 4/ ϵ ) j , and 1 − ϵ / 4 > ϵ 2 / 2 1-\epsilon/4 > \epsilon^2/2 1 − ϵ /4 > ϵ 2 /2 . Hence this side is { p j } \{p_j\} { p j } , a dumbbell with m m m points covers m − 1 m-1 m − 1 pairs, and the dumbbells of every ϵ \epsilon ϵ -WSPD of these points have at least ( n 2 ) \binom{n}{2} ( 2 n ) points in total.
The quadtree construction is a variant of the WSPD construction on a compressed quadtree [14 Chapter 3] . That construction replaces the larger of two cells that are not separated by its children, and tests separation on the cells. Ours replaces both cells, so it outputs pairs of cells of the same level. We analyze it with separation tested on the cells and on the points. For the net-tree construction in doubling metrics, a bound of O ( O P T ε ) O(\mathrm{OPT}_{\varepsilon}) O ( OPT ε ) is proved in [5 Section 4] by a similar charging to an optimal WSPD. We make the constant explicit in the plane. The randomized algorithm uses a randomly shifted quadtree [2 ] , [14 Chapter 11] , together with a random scale common to all levels, as in the tree embeddings of [11 ] .
Since translations preserve separation, we assume that P ⊂ [ 0 , L ) 2 P \subset[0,L)^2 P ⊂ [ 0 , L ) 2 for some L > 0 L > 0 L > 0 . The construction uses a square R 0 = o + [ 0 , S ) 2 R_0 = o + [0,S)^2 R 0 = o + [ 0 , S ) 2 that contains P P P , with o ∈ R 2 o \in\mathbb{R}^2 o ∈ R 2 and S ≥ L S \ge L S ≥ L . The deterministic algorithm uses o = ( 0 , 0 ) o = (0,0) o = ( 0 , 0 ) and S = L S = L S = L . The randomized algorithm draws U U U uniformly from [ 0 , 1 ) [0,1) [ 0 , 1 ) , sets S = 2 1 + U L S = 2^{1+U}L S = 2 1 + U L , and draws o o o uniformly from ( − S / 2 , 0 ] 2 (-S/2,0]^2 ( − S /2 , 0 ] 2 . Then R 0 R_0 R 0 contains [ 0 , L ) 2 [0,L)^2 [ 0 , L ) 2 , because o + S > S / 2 ≥ L o + S > S/2 \ge L o + S > S /2 ≥ L in each coordinate. For an integer i ≥ 0 i \ge0 i ≥ 0 , let s i = 2 − i S s_i = 2^{-i}S s i = 2 − i S . The cells of level i i i are the 4 i 4^i 4 i squares o + [ a s i , ( a + 1 ) s i ) × [ b s i , ( b + 1 ) s i ) o + [as_i,(a+1)s_i) \times[bs_i,(b+1)s_i) o + [ a s i , ( a + 1 ) s i ) × [ b s i , ( b + 1 ) s i ) with integers 0 ≤ a , b < 2 i 0 \le a,b < 2^i 0 ≤ a , b < 2 i . Every point of R 0 R_0 R 0 lies in exactly one cell of each level, and every cell of level i i i lies in exactly one cell of each level j ≤ i j \le i j ≤ i , its ancestor of level j j j . For a cell c c c , let P c = P ∩ c P_c = P \cap c P c = P ∩ c . For two distinct cells c c c and c ′ c' c ′ of the same level such that P c P_c P c and P c ′ P_{c'} P c ′ are nonempty, the box test accepts if the diameter of the cells is at most ε \varepsilon ε times the distance between them, and the exact test accepts if { P c , P c ′ } \{P_c,P_{c'}\} { P c , P c ′ } is ε \varepsilon ε -separated. Fix one of the two tests. A cell dumbbell is a set { c , c ′ } \{c,c'\} { c , c ′ } of two such cells that the test accepts. Then { P c , P c ′ } \{P_c,P_{c'}\} { P c , P c ′ } is ε \varepsilon ε -separated, since P c ⊆ c P_c \subseteq c P c ⊆ c and P c ′ ⊆ c ′ P_{c'} \subseteq c' P c ′ ⊆ c ′ . A cell dumbbell covers the pairs covered by { P c , P c ′ } \{P_c,P_{c'}\} { P c , P c ′ } . A cell dumbbell { c , c ′ } \{c,c'\} { c , c ′ } of level i i i is maximal if, for every j < i j < i j < i , the ancestors of c c c and c ′ c' c ′ of level j j j do not form a cell dumbbell. Let W □ \mathcal{W}_{\Box} W □ be the collection of the dumbbells { P c , P c ′ } \{P_c,P_{c'}\} { P c , P c ′ } over all maximal cell dumbbells { c , c ′ } \{c,c'\} { c , c ′ } . We show that W □ \mathcal{W}_{\Box} W □ satisfies the size bounds of Theorem 19 with both tests, and the running time with the box test.
Figure 22. (a) The cells of level i i i met by the sides X X X and Y Y Y of an optimal dumbbell are shaded. Every dumbbell of W □ \mathcal{W}_{\Box} W □ charged to { X , Y } \{X,Y\} { X , Y } is determined by a pair of shaded cells, such as the blue pair (the distance is not to scale). Here ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 and n = 5 n=5 n = 5 : X X X meets cells of a 5 × 5 5 \times5 5 × 5 block, but not two opposite corners of it. (b) The lower-left corners of the cells that meet X X X (filled dots) lie in C + [ − s , 0 ] 2 C + [-s,0]^2 C + [ − s , 0 ] 2 , where C C C is the convex hull of X X X . Other points of the grid may lie in it too (hollow dots).
Theorem 19. For P ⊂ R 2 P \subset\mathbb{R}^2 P ⊂ R 2 and ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 , a partition ε \varepsilon ε -WSPD of size at most 529 O P T ε 529\mathrm{OPT}_{\varepsilon} 529 OPT ε can be computed in O ( n log n + O P T ε ) O(n\log n+\mathrm{OPT}_{\varepsilon}) O ( n log n + OPT ε ) time, and a randomized algorithm with the same running time computes one of expected size at most 252 O P T ε 252\mathrm{OPT}_{\varepsilon} 252 OPT ε , where a dumbbell is given as a pair of
nodes of a compressed quadtree. For P ⊂ R d P \subset\mathbb{R}^d P ⊂ R d , one of size at most ( ⌊ 2 d ( 1 + 2 ε ) ⌋ + 2 ) 2 2 d O P T ε \left(\left\lfloor2\sqrt{d}(1+2\varepsilon)\right\rfloor+2\right)2^{2d}\mathrm{OPT}_{\varepsilon} ( ⌊ 2 d ( 1 + 2 ε ) ⌋ + 2 ) 2 2 d OPT ε can be computed in polynomial time.
Proof. Partition. Let { x , y } \{x,y\} { x , y } be a pair, and let c i c_i c i and c i ′ c'_i c i ′ be the cells of level i i i that contain x x x and y y y , respectively. A cell dumbbell of level i i i covers { x , y } \{x,y\} { x , y } only if it is { c i , c i ′ } \{c_i,c'_i\} { c i , c i ′ } . For i i i large enough, c i ≠ c i ′ c_i \ne c'_i c i = c i ′ and both tests accept, the exact test because P c i = { x } P_{c_i}=\{x\} P c i = { x } and P c i ′ = { y } P_{c'_i}=\{y\} P c i ′ = { y } , and the box test because the diameter of the cells tends to 0 0 0 and their distance to ∣ x y ∣ \lvert xy\rvert ∣ x y ∣ . So { c i , c i ′ } \{c_i,c'_i\} { c i , c i ′ } is a cell dumbbell. Let i 0 i_0 i 0 be the smallest level for which { c i 0 , c i 0 ′ } \{c_{i_0},c'_{i_0}\} { c i 0 , c i 0 ′ } is a cell dumbbell. It is maximal, and no cell dumbbell { c i , c i ′ } \{c_i,c'_i\} { c i , c i ′ } with i > i 0 i>i_0 i > i 0 is maximal, because its ancestors of level i 0 i_0 i 0 form a cell dumbbell. Hence exactly one maximal cell dumbbell covers { x , y } \{x,y\} { x , y } . In particular, distinct maximal cell dumbbells cover different pairs and give distinct dumbbells, so W □ \mathcal{W}_{\Box} W □ is a partition ε \varepsilon ε -WSPD.
Size. Fix a minimum ε \varepsilon ε -WSPD W ∗ \mathcal{W}^* W ∗ . Charge every dumbbell of W □ \mathcal{W}_{\Box} W □ to a dumbbell of W ∗ \mathcal{W}^* W ∗ that covers one of its pairs. Let Z = { X , Y } ∈ W ∗ Z=\{X,Y\}\in\mathcal{W}^* Z = { X , Y } ∈ W ∗ , let ℓ = dist ( X , Y ) \ell=\operatorname{dist}(X,Y) ℓ = dist ( X , Y ) , and let δ = ε ℓ / ( 1 + 2 ε ) \delta=\varepsilon\ell/(1+2\varepsilon) δ = ε ℓ / ( 1 + 2 ε ) , so that δ = ε ( ℓ − 2 δ ) \delta=\varepsilon(\ell-2\delta) δ = ε ( ℓ − 2 δ ) . Since δ < ℓ < 2 L ≤ 2 S \delta<\ell<\sqrt{2}L\le\sqrt{2}S δ < ℓ < 2 L ≤ 2 S , there is a level i ≥ 1 i\ge1 i ≥ 1 whose cells have side s = s i s=s_i s = s i with δ / ( 2 2 ) < s ≤ δ / 2 \delta/(2\sqrt{2})<s\le\delta/\sqrt{2} δ / ( 2 2 ) < s ≤ δ / 2 . Its cells have diameter at most δ \delta δ . Let x ∈ X x\in X x ∈ X and y ∈ Y y\in Y y ∈ Y , and let c c c and c ′ c' c ′ be the cells of level i i i that contain them. Every point of c c c is within distance δ \delta δ of x x x , and every point of c ′ c' c ′ is within distance δ \delta δ of y y y . Hence dist ( c , c ′ ) ≥ ℓ − 2 δ > 0 \operatorname{dist}(c,c')\ge\ell-2\delta>0 dist ( c , c ′ ) ≥ ℓ − 2 δ > 0 , so c ≠ c ′ c\ne c' c = c ′ , and since δ = ε ( ℓ − 2 δ ) \delta=\varepsilon(\ell-2\delta) δ = ε ( ℓ − 2 δ ) , the box test accepts. Then the exact test accepts as well, so { c , c ′ } \{c,c'\} { c , c ′ } is a cell dumbbell. By the first part, the maximal cell dumbbell that covers { x , y } \{x,y\} { x , y } is formed by the ancestors of c c c and c ′ c' c ′ of some level, so it is determined by { c , c ′ } \{c,c'\} { c , c ′ } . Therefore, the number of dumbbells charged to Z Z Z is at most K X K Y K_XK_Y K X K Y , where K X K_X K X and K Y K_Y K Y are the numbers of cells of level i i i that meet X X X and Y Y Y , respectively (Figure 22a).
Cells met by a small set. For D > 0 D>0 D > 0 , let m = ⌈ D ⌉ + 1 m=\lceil D\rceil+1 m = ⌈ D ⌉ + 1 , and let κ ( D ) = m 2 − 2 \kappa(D)=m^2-2 κ ( D ) = m 2 − 2 if D ≤ ( m − 2 ) 2 D\le(m-2)\sqrt{2} D ≤ ( m − 2 ) 2 and κ ( D ) = m 2 \kappa(D)=m^2 κ ( D ) = m 2 otherwise. We claim that a set A A A of diameter at most D s Ds D s meets at most κ ( D ) \kappa(D) κ ( D ) cells of level i i i . If two points of A A A lie in cells whose columns differ by j ≥ 1 j\ge1 j ≥ 1 , their first coordinates differ by more than ( j − 1 ) s (j-1)s ( j − 1 ) s , so j − 1 < D j-1<D j − 1 < D and j ≤ m − 1 j\le m-1 j ≤ m − 1 . Hence A A A meets at most m m m columns and, similarly, at most m m m rows. If it meets fewer than m m m columns or fewer than m m m rows, it meets at most m ( m − 1 ) ≤ m 2 − 2 m(m-1)\le m^2-2 m ( m − 1 ) ≤ m 2 − 2 cells. Otherwise, it meets only cells of an m × m m\times m m × m block. Two points in opposite corner cells of this block are at distance more than ( m − 2 ) 2 s (m-2)\sqrt{2}\,s ( m − 2 ) 2 s , so if D ≤ ( m − 2 ) 2 D\le(m-2)\sqrt{2} D ≤ ( m − 2 ) 2 , then A A A meets at most one cell of each of the two pairs of opposite corners.
Deterministic bound. We have diam ( X ) < ε ℓ = ( 1 + 2 ε ) δ < 2 2 ( 1 + 2 ε ) s \operatorname{diam}(X)<\varepsilon\ell=(1+2\varepsilon)\delta<2\sqrt{2}(1+2\varepsilon)s diam ( X ) < ε ℓ = ( 1 + 2 ε ) δ < 2 2 ( 1 + 2 ε ) s , and 2 2 ( 1 + 2 ε ) < 3.96 2\sqrt{2}(1+2\varepsilon)<3.96 2 2 ( 1 + 2 ε ) < 3.96 for ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 . For D = 3.96 D=3.96 D = 3.96 , we have m = 5 m=5 m = 5 and D ≤ 3 2 D\le3\sqrt{2} D ≤ 3 2 , so K X ≤ κ ( D ) = 23 K_X\le\kappa(D)=23 K X ≤ κ ( D ) = 23 . The same holds for Y Y Y . Hence at most 23 2 = 529 23^2=529 2 3 2 = 529 dumbbells are charged to Z Z Z , and ∣ W □ ∣ ≤ 529 ∣ W ∗ ∣ \lvert\mathcal{W}_{\Box}\rvert\le529\lvert\mathcal{W}^*\rvert ∣ W □ ∣ ≤ 529 ∣ W ∗ ∣ .
Randomized bound. In the randomized algorithm, s = 2 1 + U − i L s=2^{1+U-i}L s = 2 1 + U − i L , and the level i i i depends only on U U U (for fixed Z Z Z ). Let V = log 2 ( δ / ( 2 s ) ) V=\log_2(\delta/(\sqrt{2}s)) V = log 2 ( δ / ( 2 s )) . Then V ∈ [ 0 , 1 ) V\in[0,1) V ∈ [ 0 , 1 ) and V = log 2 ( δ / ( 2 2 L ) ) − U + i V=\log_2(\delta/(2\sqrt{2}L))-U+i V = log 2 ( δ / ( 2 2 L )) − U + i , so V V V is the fractional part of log 2 ( δ / ( 2 2 L ) ) − U \log_2(\delta/(2\sqrt{2}L))-U log 2 ( δ / ( 2 2 L )) − U , and it is uniformly distributed in [ 0 , 1 ) [0,1) [ 0 , 1 ) . Let γ = 1.4 2 \gamma=1.4\sqrt{2} γ = 1.4 2 and D V = γ 2 V D_V=\gamma2^V D V = γ 2 V . For ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 , diam ( X ) ≤ ( 1 + 2 ε ) δ = ( 1 + 2 ε ) 2 2 V s ≤ D V s \operatorname{diam}(X)\le(1+2\varepsilon)\delta=(1+2\varepsilon)\sqrt{2}2^Vs\le D_Vs diam ( X ) ≤ ( 1 + 2 ε ) δ = ( 1 + 2 ε ) 2 2 V s ≤ D V s , and the same holds for Y Y Y , so K Y ≤ κ ( D V ) K_Y\le\kappa(D_V) K Y ≤ κ ( D V ) .
Fix U U U . The lower-left corners of the cells of level i i i lie in the lattice o + s Z 2 o+s\mathbb{Z}^2 o + s Z 2 . Since i ≥ 1 i\ge1 i ≥ 1 , S / 2 = 2 i − 1 s S/2=2^{i-1}s S /2 = 2 i − 1 s is a multiple of s s s , so each coordinate of o o o is uniformly distributed modulo s s s , and the lattice is a uniformly random translate of s Z 2 s\mathbb{Z}^2 s Z 2 . The expected number of its points in a measurable set is the area of the set divided by s 2 s^2 s 2 . The cell with lower-left corner g g g meets X X X if and only if g ∈ X + ( − s , 0 ] 2 g\in X+(-s,0]^2 g ∈ X + ( − s , 0 ] 2 . This set is contained in C + [ − s , 0 ] 2 C+[-s,0]^2 C + [ − s , 0 ] 2 , where C C C is the convex hull of X X X . Let w 1 , w 2 ≤ diam ( X ) w_1,w_2\le\operatorname{diam}(X) w 1 , w 2 ≤ diam ( X ) be the widths of C C C along the two axes. By Cavalieri’s principle, adding a horizontal segment of length s s s to a convex set increases its area by s s s times its vertical width, and similarly for a vertical segment, so the area of C + [ − s , 0 ] 2 C+[-s,0]^2 C + [ − s , 0 ] 2 is area ( C ) + s ( w 1 + w 2 ) + s 2 \operatorname{area}(C)+s(w_1+w_2)+s^2 area ( C ) + s ( w 1 + w 2 ) + s 2 (Figure 22b). By the isodiametric inequality, area(C C C ) ≤ π diam ( X ) 2 / 4 \le\pi\operatorname{diam}(X)^2/4 ≤ π diam ( X ) 2 /4 . Therefore, E [ K X ∣ U ] ≤ e ( D V ) \mathbb{E}[K_X \mid U] \le e(D_V) E [ K X ∣ U ] ≤ e ( D V ) , where e ( D ) = π D 2 / 4 + 2 D + 1 e(D) = \pi D^2/4 + 2D + 1 e ( D ) = π D 2 /4 + 2 D + 1 . Since K Y ≤ κ ( D V ) K_Y \le\kappa(D_V) K Y ≤ κ ( D V ) , we get E [ K X K Y ∣ U ] ≤ κ ( D V ) e ( D V ) \mathbb{E}[K_XK_Y \mid U] \le\kappa(D_V)e(D_V) E [ K X K Y ∣ U ] ≤ κ ( D V ) e ( D V ) . With the substitution D = γ 2 v D = \gamma2^v D = γ 2 v ,
E [ K X K Y ] ≤ ∫ 0 1 κ ( γ 2 v ) e ( γ 2 v ) d v = 1 ln 2 ∫ γ 2 γ κ ( D ) ( π D 4 + 2 + 1 D ) d D . \mathbb{E}[K_XK_Y] \le\int_0^1 \kappa(\gamma2^v)e(\gamma2^v)\,dv = \frac{1}{\ln2}\int_\gamma^{2\gamma}\kappa(D)\left(\frac{\pi D}{4}+2+\frac{1}{D}\right)\,dD. E [ K X K Y ] ≤ ∫ 0 1 κ ( γ 2 v ) e ( γ 2 v ) d v = ln 2 1 ∫ γ 2 γ κ ( D ) ( 4 π D + 2 + D 1 ) d D .
The function κ \kappa κ equals 9 on [ γ , 2 ] [\gamma,2] [ γ , 2 ] , 14 on ( 2 , 2 2 ] (2,2\sqrt{2}] ( 2 , 2 2 ] , 16 on ( 2 2 , 3 ] (2\sqrt{2},3] ( 2 2 , 3 ] , and 23 on ( 3 , 2 γ ] (3,2\gamma] ( 3 , 2 γ ] . With the antiderivative π D 2 / 8 + 2 D + ln D \pi D^2/8+2D+\ln D π D 2 /8 + 2 D + ln D , the right side is less than 251.6. Summing over the dumbbells of W ∗ W^* W ∗ gives E ∣ W □ ∣ ≤ 252 ∣ W ∗ ∣ \mathbb{E}|W_{\square}| \le252|W^*| E ∣ W □ ∣ ≤ 252∣ W ∗ ∣ .
Running time. We use the compressed quadtree of P P P , which is computed in O ( n log n ) O(n\log n) O ( n log n ) time in the real RAM with the floor and logarithm functions [14 ] . For every node c c c of the compressed quadtree and every two distinct cells a , b ⊆ c a,b\subseteq c a , b ⊆ c of the next level such that P a P_a P a and P b P_b P b are nonempty, we call Visit( a , b ) (a,b) ( a , b ) . Consider a call Visit( c , c ′ ) (c,c') ( c , c ′ ) . If P c P_c P c and P c ′ P_{c'} P c ′ are single points, it outputs { P c , P c ′ } \{P_c,P_{c'}\} { P c , P c ′ } . Otherwise, let j j j be the smallest level greater than that of c c c at which P c P_c P c or P c ′ P_{c'} P c ′ meets at least two cells; it is found in the compressed quadtree. From the level of c c c to level j − 1 j-1 j − 1 , the cells that contain P c P_c P c and P c ′ P_{c'} P c ′ contain no other point. If the two cells of one of these levels form a cell dumbbell, then so do those of level j − 1 j-1 j − 1 : the exact test gives the same answer at all these levels, and the box test is monotone, because from a level to the next the diameter of the cells halves and their distance does not decrease. Therefore, the call tests the two cells of level j − 1 j-1 j − 1 and outputs { P c , P c ′ } \{P_c,P_{c'}\} { P c , P c ′ } if the test accepts. Otherwise, it makes a call Visit( a , b ) (a,b) ( a , b ) for every nonempty cell a ⊆ c a\subseteq c a ⊆ c and every nonempty cell b ⊆ c ′ b\subseteq c' b ⊆ c ′ of level j j j . Hence the calls output exactly the dumbbells of W □ W_{\square} W □ , each as a pair of nodes of the compressed quadtree. Every call that outputs nothing makes at least two calls, and there are O ( n ) O(n) O ( n ) initial calls, so there are O ( n + ∣ W □ ∣ ) O(n+|W_{\square}|) O ( n + ∣ W □ ∣ ) calls in total. The deterministic bound holds for every square R 0 R_0 R 0 that contains P P P , so ∣ W □ ∣ ≤ 529 OPT ε |W_{\square}|\le529\operatorname{OPT}_{\varepsilon} ∣ W □ ∣ ≤ 529 OPT ε in the randomized algorithm too, and there are O ( n + OPT ε ) O(n+\operatorname{OPT}_{\varepsilon}) O ( n + OPT ε ) calls. With the box test, a call takes O ( 1 ) O(1) O ( 1 ) time, since the two cells of level j − 1 j-1 j − 1 are computed from one point of P c P_c P c and one point of P c ′ P_{c'} P c ′ with the floor function, and the total time is O ( n log n + OPT ε ) O(n\log n+\operatorname{OPT}_{\varepsilon}) O ( n log n + OPT ε ) . This is O ( n log n + n / ε 2 ) O(n\log n+n/\varepsilon^2) O ( n log n + n / ε 2 ) , since OPT ε = O ( n / ε 2 ) \operatorname{OPT}_{\varepsilon}=O(n/\varepsilon^2) OPT ε = O ( n / ε 2 ) by the CK construction [7 ] . With the exact test, a call takes O ( n log n ) O(n\log n) O ( n log n ) time, computing the diameters from the convex hulls and the distance from the Delaunay triangulation of P c ∪ P c ′ P_c\cup P_{c'} P c ∪ P c ′ , which contains a closest pair with one point in each side, and the total time is O ( ( n + OPT ε ) n log n ) O((n+\operatorname{OPT}_{\varepsilon})n\log n) O (( n + OPT ε ) n log n ) , which is O ( n 2 min { n , 1 / ε 2 } log n ) O(n^2\min\{n,1/\varepsilon^2\}\log n) O ( n 2 min { n , 1/ ε 2 } log n ) since also OPT ε ≤ ( n 2 ) \operatorname{OPT}_{\varepsilon}\le\binom{n}{2} OPT ε ≤ ( 2 n ) . Drawing R 0 R_0 R 0 takes O ( 1 ) O(1) O ( 1 ) time.
Higher dimensions. The deterministic bound extends with cubes of diameter d s \sqrt{d}s d s in place of squares: the projection of X X X on each axis is an interval of length less than 2 d ( 1 + 2 ε ) s 2\sqrt{d}(1+2\varepsilon)s 2 d ( 1 + 2 ε ) s , which meets at most ⌈ 2 d ( 1 + 2 ε ) ⌉ + 2 \lceil2\sqrt{d}(1+2\varepsilon)\rceil+2 ⌈ 2 d ( 1 + 2 ε )⌉ + 2 of the intervals [ a s , ( a + 1 ) s ) [as,(a+1)s) [ a s , ( a + 1 ) s ) .
The exact test never gives more dumbbells than the box test. Every cell dumbbell of the box test is also a cell dumbbell of the exact test, so every maximal cell dumbbell of the box test lies in a unique maximal cell dumbbell of the exact test, formed by ancestors of its cells. Every maximal cell dumbbell of the exact test covers some pair and therefore contains the maximal cell dumbbell of the box test that covers this pair. By Markov’s inequality, for ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 , one run of the randomized algorithm outputs more than 504 OPT ε 504\operatorname{OPT}_{\varepsilon} 504 OPT ε dumbbells with probability at most 1 / 2 1/2 1/2 , so the smallest output of k k k independent runs has size at most 504 OPT ε 504\operatorname{OPT}_{\varepsilon} 504 OPT ε with probability at least 1 − 2 − k 1-2^{-k} 1 − 2 − k . For ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , the randomized bound computed with γ = 1.125 2 \gamma=1.125\sqrt{2} γ = 1.125 2 is 141, with the same pieces of κ \kappa κ . For every ε < 1 \varepsilon<1 ε < 1 , the same proofs give the factors 98 2 = 9604 98^2=9604 9 8 2 = 9604 (with D = 6 2 D=6\sqrt{2} D = 6 2 , m = 10 m=10 m = 10 ) and 2812 (with γ = 3 2 \gamma=3\sqrt{2} γ = 3 2 ). In R d \mathbb{R}^d R d , the factor is 5 6 = 15625 5^6=15625 5 6 = 15625 for d = 3 d=3 d = 3 and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 .
Fair split trees. The charging of Theorem 19 also applies to the CK construction on a fair split tree [7 ] . We first consider the version used in Section 5, which has the tree of [7 ] but differs in the separation test and in the choice of the node that is split, and then the original construction. A box is an axis-parallel rectangle. Every node u u u of the tree T T T has a point set P u ⊆ P P_u \subseteq P P u ⊆ P , and b u b_u b u denotes the smallest box that contains P u P_u P u . The root has the point set P P P , and the leaves are the nodes with one point. Every other node u u u is split by the line through the center of b u b_u b u that is perpendicular to a longest side of b u b_u b u : the point sets of its two children are the points of P u P_u P u on each side of the line, where the points on the line go to a fixed side. For two nodes u u u and v v v with disjoint point sets, the box test accepts if max { diam ( b u ) , diam ( b v ) } ≤ ε dist ( b u , b v ) \max\{\operatorname{diam}(b_u),\operatorname{diam}(b_v)\} \leq\varepsilon\operatorname{dist}(b_u,b_v) max { diam ( b u ) , diam ( b v )} ≤ ε dist ( b u , b v ) , and the exact test accepts if the box test accepts or { P u , P v } \{P_u,P_v\} { P u , P v } is ε \varepsilon ε -separated. Fix one of the two tests. The procedure Pairs ( u , v ) \operatorname{Pairs}(u,v) Pairs ( u , v ) outputs { P u , P v } \{P_u,P_v\} { P u , P v } if the test accepts. Otherwise, it takes the node whose box has the larger diameter, say u u u , breaking ties arbitrarily, and calls Pairs ( u 1 , v ) \operatorname{Pairs}(u_1,v) Pairs ( u 1 , v ) and Pairs ( u 2 , v ) \operatorname{Pairs}(u_2,v) Pairs ( u 2 , v ) for the two children u 1 , u 2 u_1,u_2 u 1 , u 2 of u u u . This node is not a leaf, since both tests accept two leaves. Let W T W_T W T be the collection of the dumbbells output by the calls Pairs ( u 1 , u 2 ) \operatorname{Pairs}(u_1,u_2) Pairs ( u 1 , u 2 ) over all nodes of T T T with children u 1 , u 2 u_1,u_2 u 1 , u 2 , where a dumbbell is output as a pair of nodes.
Theorem 20. For P ⊂ R 2 P \subset\mathbb{R}^2 P ⊂ R 2 and ε ≤ 1 / 5 \varepsilon\leq1/5 ε ≤ 1/5 , the collection W T W_T W T is a partition ε \varepsilon ε -WSPD of size at most 1024 OPT ε 1024\operatorname{OPT}_{\varepsilon} 1024 OPT ε , both with the box test and with the exact test. With the box test, it is computed in O ( n log n + OPT ε ) O(n\log n+\operatorname{OPT}_{\varepsilon}) O ( n log n + OPT ε ) time. For P ⊂ R d P \subset\mathbb{R}^d P ⊂ R d , its size is at most ⌊ ( 2 d ( 1 + 2 ε ) + 2 ) d ⌋ 2 OPT ε \left\lfloor\left(2\sqrt{d}(1+2\varepsilon)+2\right)^d\right\rfloor^2\operatorname{OPT}_{\varepsilon} ⌊ ( 2 d ( 1 + 2 ε ) + 2 ) d ⌋ 2 OPT ε .
Proof. Partition. Every dumbbell of W T W_T W T is ε \varepsilon ε -separated, because P u ⊆ b u P_u \subseteq b_u P u ⊆ b u for every node u u u . Let { x , y } \{x,y\} { x , y } be a pair. The calls Pairs ( u , v ) \operatorname{Pairs}(u,v) Pairs ( u , v ) with x ∈ P u x \in P_u x ∈ P u and y ∈ P v y \in P_v y ∈ P v , or vice versa, form a chain: it starts with the call for the two children of the lowest common ancestor of the leaves of x x x and y y y , and every call of the chain that outputs nothing makes exactly one call of the chain, and the chain ends with an output, since two leaves are accepted. Hence exactly one dumbbell of W T W_T W T covers { x , y } \{x,y\} { x , y } .
Size. Fix a minimum ε \varepsilon ε -WSPD W ∗ W^* W ∗ , and charge every dumbbell of W T W_T W T to a dumbbell of W ∗ W^* W ∗ that covers one of its pairs. Let Z = { X , Y } ∈ W ∗ Z=\{X,Y\}\in W^* Z = { X , Y } ∈ W ∗ , and let ℓ = dist ( X , Y ) \ell=\operatorname{dist}(X,Y) ℓ = dist ( X , Y ) and δ = ε ℓ / ( 1 + 2 ε ) \delta=\varepsilon\ell/(1+2\varepsilon) δ = ε ℓ / ( 1 + 2 ε ) , as in the proof of Theorem 19 . We regard a node as an ancestor of itself. The diameter of the box does not decrease from a node to its parent. For a point x x x , let u ( x ) u(x) u ( x ) be the highest ancestor of the leaf of x x x whose box has diameter at most δ \delta δ . The box of the root has diameter at least ℓ > δ \ell>\delta ℓ > δ , so u ( x ) u(x) u ( x ) is not the root, and the box of every proper ancestor of u ( x ) u(x) u ( x ) has diameter greater than δ \delta δ .
Let x ∈ X x\in X x ∈ X and y ∈ Y y\in Y y ∈ Y . Every point of b u ( x ) b_{u(x)} b u ( x ) is within distance δ \delta δ of x x x , and every point of b u ( y ) b_{u(y)} b u ( y ) is within distance δ \delta δ of y y y . Hence dist ( b u ( x ) , b u ( y ) ) ≥ ℓ − 2 δ > 0 \operatorname{dist}(b_{u(x)},b_{u(y)})\geq\ell-2\delta>0 dist ( b u ( x ) , b u ( y ) ) ≥ ℓ − 2 δ > 0 , and since δ = ε ( ℓ − 2 δ ) \delta=\varepsilon(\ell-2\delta) δ = ε ( ℓ − 2 δ ) , both tests accept u ( x ) u(x) u ( x ) and u ( y ) u(y) u ( y ) . In particular, P u ( x ) P_{u(x)} P u ( x ) and P u ( y ) P_{u(y)} P u ( y ) are disjoint, so the first call of the chain of { x , y } \{x,y\} { x , y } is on proper ancestors of u ( x ) u(x) u ( x ) and u ( y ) u(y) u ( y ) or on these nodes themselves. We claim that every call Pairs ( u , v ) \operatorname{Pairs}(u,v) Pairs ( u , v ) of the chain, with x ∈ P u x\in P_u x ∈ P u , is on an ancestor of u ( x ) u(x) u ( x ) and an ancestor v v v of u ( y ) u(y) u ( y ) . Consider such a call that outputs nothing. Then u ≠ u ( x ) u\ne u(x) u = u ( x ) or v ≠ u ( y ) v\ne u(y) v = u ( y ) . If u = u ( x ) u=u(x) u = u ( x ) , then v v v is a proper ancestor of u ( y ) u(y) u ( y ) , so diam ( b v ) > δ ≥ diam ( b u ) \operatorname{diam}(b_v)>\delta\geq\operatorname{diam}(b_u) diam ( b v ) > δ ≥ diam ( b u ) and the call splits v v v . Similarly, if v = u ( y ) v=u(y) v = u ( y ) , the call splits u u u . Otherwise, both nodes are proper ancestors. In each case, the next call of the chain is on ancestors of u ( x ) u(x) u ( x ) and u ( y ) u(y) u ( y ) . Therefore, the dumbbell of W T W_T W T that covers { x , y } \{x,y\} { x , y } is output by a call on ancestors of u ( x ) u(x) u ( x ) and u ( y ) u(y) u ( y ) . The calls of the chain depend only on these ancestors, so this dumbbell is determined by u ( x ) u(x) u ( x ) and u ( y ) u(y) u ( y ) . The number of dumbbells charged to Z Z Z is thus at most K X K Y K_XK_Y K X K Y , where K X K_X K X is the number of distinct nodes u ( x ) u(x) u ( x ) with x ∈ X x\in X x ∈ X , and K Y K_Y K Y the number of distinct nodes u ( y ) u(y) u ( y ) with y ∈ Y y\in Y y ∈ Y .
Packing. We bound K X K_X K X using the outer rectangles of [7 ] . Let λ u \lambda_u λ u be the length of a longest side of b u b_u b u . The outer rectangle b ^ u \hat{b}_u b ^ u of the root u u u is a square of side λ u \lambda_u λ u that contains b u b_u b u . For a child u u u of a node v v v , b ^ u \hat{b}_u b ^ u is the part of b ^ v \hat{b}_v b ^ v on the side of P u P_u P u of the line that splits v v v . Then b u ⊆ b ^ u b_u \subseteq\hat{b}_u b u ⊆ b ^ u , and the outer rectangles of two nodes have disjoint interiors if neither is an ancestor of the other. Moreover, both sides of b ^ u \hat{b}_u b ^ u have length at least λ v / 2 \lambda_v/2 λ v /2 , where v v v is the parent of u u u . For the sides perpendicular to the line that splits v v v , this holds because b v ⊆ b ^ v b_v \subseteq\hat{b}_v b v ⊆ b ^ v extends λ v / 2 \lambda_v/2 λ v /2 on each side of the line. The other sides are as long as those of b ^ v \hat{b}_v b ^ v , whose length is λ v \lambda_v λ v if v v v is the root, and at least λ v ′ / 2 ≥ λ v / 2 \lambda_{v'}/2 \ge\lambda_v/2 λ v ′ /2 ≥ λ v /2 by induction otherwise, where v ′ v' v ′ is the parent of v v v .
Let m = δ / ( 2 2 ) m = \delta/(2\sqrt{2}) m = δ / ( 2 2 ) . The box of the parent v v v of u ( x ) u(x) u ( x ) has diameter greater than δ \delta δ , so λ v > δ / 2 \lambda_v > \delta/\sqrt{2} λ v > δ / 2 and both sides of b ^ u ( x ) \hat{b}_{u(x)} b ^ u ( x ) are longer than m m m . Hence b ^ u ( x ) \hat{b}_{u(x)} b ^ u ( x ) contains an axis-parallel square of side m m m that contains x x x . No node u ( x ) u(x) u ( x ) is a proper ancestor of another one, so these squares, one for each of the K X K_X K X nodes, have disjoint interiors. They lie in C + [ − m , m ] 2 C + [-m,m]^2 C + [ − m , m ] 2 , where C C C is the convex hull of X X X . As in the proof of Theorem 19 , the area of this set is area ( C ) + 2 m ( w 1 + w 2 ) + 4 m 2 \operatorname{area}(C) + 2m(w_1 + w_2) + 4m^2 area ( C ) + 2 m ( w 1 + w 2 ) + 4 m 2 , where w 1 , w 2 ≤ diam ( X ) w_1,w_2 \le\operatorname{diam}(X) w 1 , w 2 ≤ diam ( X ) are the widths of C C C along the two axes, and area ( C ) ≤ π diam ( X ) 2 / 4 \operatorname{area}(C) \le\pi\operatorname{diam}(X)^2/4 area ( C ) ≤ π diam ( X ) 2 /4 . If diam ( X ) ≤ D m \operatorname{diam}(X) \le Dm diam ( X ) ≤ D m , the area is thus at most ( π D 2 / 4 + 4 D + 4 ) m 2 (\pi D^2/4 + 4D + 4)m^2 ( π D 2 /4 + 4 D + 4 ) m 2 . We have diam ( X ) ≤ ε ℓ = ( 1 + 2 ε ) δ = 2 2 ( 1 + 2 ε ) m \operatorname{diam}(X) \le\varepsilon\ell= (1 + 2\varepsilon)\delta= 2\sqrt{2}(1 + 2\varepsilon)m diam ( X ) ≤ ε ℓ = ( 1 + 2 ε ) δ = 2 2 ( 1 + 2 ε ) m , which is less than 3.96 m 3.96m 3.96 m for ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 . Hence K X ≤ π D 2 / 4 + 4 D + 4 < 33 K_X \le\pi D^2/4 + 4D + 4 < 33 K X ≤ π D 2 /4 + 4 D + 4 < 33 for D = 3.96 D = 3.96 D = 3.96 , that is, K X ≤ 32 K_X \le32 K X ≤ 32 , and the same holds for K Y K_Y K Y . At most 32 2 = 1024 32^2 = 1024 3 2 2 = 1024 dumbbells are charged to Z Z Z , and ∣ W T ∣ ≤ 1024 ∣ W ∗ ∣ |W_T| \le1024|W^*| ∣ W T ∣ ≤ 1024∣ W ∗ ∣ .
Running time. The tree is computed in O ( n log n ) O(n\log n) O ( n log n ) time [7 ] . Every call that outputs nothing makes two calls, and there are n − 1 n - 1 n − 1 initial calls, so there are O ( n + ∣ W T ∣ ) O(n + |W_T|) O ( n + ∣ W T ∣ ) calls. With the box test, a call takes O ( 1 ) O(1) O ( 1 ) time. Since ∣ W T ∣ ≤ 1024 OPT ε |W_T| \le1024\operatorname{OPT}_{\varepsilon} ∣ W T ∣ ≤ 1024 OPT ε , the total time is O ( n log n + OPT ε ) O(n\log n + \operatorname{OPT}_{\varepsilon}) O ( n log n + OPT ε ) , which is O ( n log n + n / ε 2 ) O(n\log n + n/\varepsilon^2) O ( n log n + n / ε 2 ) since OPT ε = O ( n / ε 2 ) \operatorname{OPT}_{\varepsilon} = O(n/\varepsilon^2) OPT ε = O ( n / ε 2 ) [7 ] .
Higher dimensions. In R d \mathbb{R}^d R d , a node is split by the hyperplane through the center of its box that is perpendicular to a longest side, and the same proof applies with m = δ / ( 2 d ) m = \delta/(2\sqrt{d}) m = δ / ( 2 d ) : the outer box of u ( x ) u(x) u ( x ) contains a cube of side m m m that contains x x x , and X X X lies in a cube of side diam ( X ) ≤ 2 d ( 1 + 2 ε ) m \operatorname{diam}(X) \le2\sqrt{d}(1 + 2\varepsilon)m diam ( X ) ≤ 2 d ( 1 + 2 ε ) m . These cubes lie in a cube of side diam ( X ) + 2 m \operatorname{diam}(X) + 2m diam ( X ) + 2 m , so K X ≤ ( 2 d ( 1 + 2 ε ) + 2 ) d K_X \le(2\sqrt{d}(1 + 2\varepsilon) + 2)^d K X ≤ ( 2 d ( 1 + 2 ε ) + 2 ) d . ◀
For ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , the same proof gives the factor 24 2 = 576 24^2 = 576 2 4 2 = 576 (with D = 1.125 ⋅ 2 2 D = 1.125 \cdot2\sqrt{2} D = 1.125 ⋅ 2 2 ), and for every ε < 1 \varepsilon< 1 ε < 1 , the factor 94 2 = 8836 94^2 = 8836 9 4 2 = 8836 (with D = 6 2 D = 6\sqrt{2} D = 6 2 ). In R 3 \mathbb{R}^3 R 3 , the factor is 205 2 = 42025 205^2 = 42025 20 5 2 = 42025 for ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 . With the exact test, a call takes O ( n log n ) O(n\log n) O ( n log n ) time, as in the proof of Theorem 19 . The proof also applies to the original construction of [7 ] , with two changes. First, its test, for a separation s > 0 s > 0 s > 0 , accepts two nodes u u u and v v v if b u b_u b u and b v b_v b v are contained in two balls of the same radius r r r that are at distance at least s r sr sr from each other. For s = 2 / ε s = 2/\varepsilon s = 2/ ε , this test accepts only ε \varepsilon ε -separated dumbbells, since diam ( P u ) , diam ( P v ) ≤ 2 r \operatorname{diam}(P_u),\operatorname{diam}(P_v) \le2r diam ( P u ) , diam ( P v ) ≤ 2 r and dist ( P u , P v ) ≥ 2 r / ε \operatorname{dist}(P_u,P_v) \ge2r/\varepsilon dist ( P u , P v ) ≥ 2 r / ε . It accepts u ( x ) u(x) u ( x ) and u ( y ) u(y) u ( y ) : for r = max { diam ( b u ( x ) ) , diam ( b u ( y ) ) } / 2 ≤ δ / 2 r = \max\{\operatorname{diam}(b_{u(x)}),\operatorname{diam}(b_{u(y)})\}/2 \le\delta/2 r = max { diam ( b u ( x ) ) , diam ( b u ( y ) )} /2 ≤ δ /2 , every point of the balls of radius r r r centered at the centers of the two boxes is within distance 2 r ≤ δ 2r \le\delta 2 r ≤ δ of x x x or of y y y , so the distance between the balls is at least ℓ − 2 δ = δ ≥ s r \ell- 2\delta= \delta\ge sr ℓ − 2 δ = δ ≥ sr . Second, PAIRS splits the node whose box has the longer side. Then u ( x ) u(x) u ( x ) is defined as the highest ancestor leaf of x x x with λ u ( x ) ≤ δ / 2 \lambda_{u(x)} \le\delta/\sqrt{2} λ u ( x ) ≤ δ / 2 , so that its box has diameter at most δ \delta δ and the box of its parent has a side longer than δ / 2 \delta/\sqrt{2} δ / 2 , and the rest of the proof is unchanged. Hence, for P ⊂ R 2 P \subset\mathbb{R}^2 P ⊂ R 2 and ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 , the construction of [7 ] with separation 2 / ε 2/\varepsilon 2/ ε computes a partition ε \varepsilon ε -WSPD of size at most 1024 OPT ε 1024\operatorname{OPT}_{\varepsilon} 1024 OPT ε in O ( n log n + OPT ε ) O(n\log n + \operatorname{OPT}_{\varepsilon}) O ( n log n + OPT ε ) time.
Conclusion
We gave approximation algorithms for MINWSPD with explicit factors that keep the separation ε \varepsilon ε . For cover WSPDs, the sweep is a 40-approximation in the plane for ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , a 2048-approximation in R 3 \mathbb{R}^{3} R 3 , and a 2 O ( d ) 2^{O(d)} 2 O ( d ) -approximation in R d \mathbb{R}^{d} R d . With pieces that depend on ε \varepsilon ε , it keeps a constant factor for every ε > 0 \varepsilon> 0 ε > 0 . For partition WSPDs, CK on a fair split tree and the quadtree construction give factors 1024 and 529 in the plane for ε ≤ 1 / 5 \varepsilon\le1/5 ε ≤ 1/5 , and 252 in expectation for a randomly shifted and scaled quadtree, in O ( n log n + O P T ) O(n \log n + \mathrm{OPT}) O ( n log n + OPT ) time. The sweep also gives a lower bound on OPT: its anchors are pairwise incompatible, so its number of steps is at most OPT.
On the practical side, the greedy sweep keeps the factor 40, and reshape shrinks any given WSPD without increasing its size. A local search on the anchors of the sweep enlarges its lower bound to LB, which is at least 0.989 OPT on every planar instance where OPT is known, and certifies the quality of any WSPD on inputs where OPT is out of reach. In the plane, the greedy sweep followed by reshape is within 0.02% of OPT for n = 500 n = 500 n = 500 and on average 1.05 LB for n = 10000 n = 10000 n = 10000 . Converting its output gives partition WSPDs of on average 1.13 LB, against 1.55 LB for CK. In R 3 \mathbb{R}^{3} R 3 , reshape is at most 0.03% above OPT where OPT is known, and on average 1.021 LB for n = 10000 n = 10000 n = 10000 .
Open problem. Without the final deletion of redundant dumbbells, which can only decrease the size, the largest ratio we observed between the output of the greedy sweep and the smallest known WSPD is 1.503, for jupiter-0020000 with ε = 1 / 20 \varepsilon= 1/20 ε = 1/20 . Hence its approximation factor for small ε \varepsilon ε is between 1.503 and 40. What is it?
The largest observed ratio grows with n n n , from 1.41 for n = 10000 n = 10000 n = 10000 to 1.50 for n = 20000 n = 20000 n = 20000 , so the lower end may be far from the truth. The upper end is the product of two bounds: the number of steps is at most OPT, and every step outputs at most 40 dumbbells. An analysis that bounds each step separately cannot improve it much: for ε = 1 / 16 \varepsilon= 1/16 ε = 1/16 , we found point sets in which the set R p q R_{pq} R pq of a single step needs 23 dumbbells. A smaller factor seems to need an amortized argument, which pays for a step whose R p q R_{pq} R pq needs many dumbbells with optimal dumbbells that cover pairs outside R p q R_{pq} R pq .