1527:
164:
1518:
reconstruct the list without the overhead of resorting the points, it is necessary to rebuild the sorted lists once all points have been assigned to their nodes. To do the rebuilding, walk along each list for each dimension, add each point to the corresponding list of its nodes, and add cross-pointers in the original list to be able to add the cross-pointers for the new lists. Finally, call the recursion on each node and his set.
3172:
2951:
1517:
To be able to maintain the sorted lists for each node, linked lists are used. Cross-pointers are kept for each list to the others to be able to retrieve a point in constant time. In the algorithm above, in each iteration of the loop, a call to the recursion is done. In reality, to be able to
3705:
3167:{\displaystyle {\begin{aligned}&{\frac {|pp'|}{2}}\leq \rho \leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&{\frac {|pp'|}{2}}\leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&|pp'|\leq {\frac {2}{s}}|pq|\\\end{aligned}}}
4157:
598:
3506:
3520:
2956:
3388:
57:
2704:
2802:
2129:. Because, each time there is a recursion, the recursion tree creates two branches that contain all the points of the current recursion call, there will be a sequence of call to
3515:
2464:
Each time the recursion tree split in two, there is one more pair added to the decomposition. So, the algorithm run-time is in the number of pairs in the final decomposition.
224:
2944:
3303:
3266:
2604:
4067:
3934:
706:
103:
3809:
843:
810:
775:
742:
4032:
3980:
3899:
3854:
3758:
2504:
1199:
938:
900:
1158:
654:
139:
3209:
2755:
2547:
2414:
1812:
2630:
1916:
1890:
1864:
1838:
459:
303:
2822:
436:
1228:
412:
383:
253:
195:
3229:
2902:
2882:
2862:
2842:
2730:
2567:
2454:
2434:
2382:
2362:
2342:
2318:
2298:
2274:
2254:
2234:
2211:
2191:
2171:
2151:
2119:
2099:
2079:
2059:
2039:
2019:
1999:
1979:
1959:
1939:
1780:
1760:
1740:
674:
622:
482:
350:
330:
277:
860:
4076:
487:
1526:
4290:
Arya, Sunil; Mount, David M. (2016). "A fast and simple algorithm for computing approximate euclidean minimum spanning trees".
4307:
256:
1071:-th dimension in two same-size hyperrectangles and take the points contained in these hyperrectangles to form the two sets
1715:
It is clear that the pairs returned by the algorithm are well-separated because of the return condition of the function
3860:
4224:"A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields"
4329:
4070:
3993:
3401:
27:
3714:
The well-separated pair decomposition has application in solving a number of problems. WSPD can be used to:
3308:
2467:
Callahan and
Kosaraju proved that this algorithm finds a Well-separated pair decomposition (WSPD) of size
3700:{\displaystyle {\begin{aligned}|p'q'|&\leq (2/s)|pq|+|pq|+(2/s)|pq|\\&=(1+4/s)|pq|\end{aligned}}}
2635:
1230:
operations per step of the recursion but only call the recursion on at most half the points each time.
2760:
200:
2907:
4040:
3907:
679:
62:
3937:
3770:
815:
782:
747:
714:
3999:
3947:
3866:
3821:
3725:
3271:
3234:
2572:
2470:
1166:
905:
866:
163:
17:
1127:
627:
112:
4255:
Bespamyatnikh, Sergei; Segal, Michael (2002). "Fast
Algorithms for Approximating Distances".
3182:
2520:
2387:
1785:
2609:
1895:
1869:
1843:
1817:
441:
282:
3719:
2807:
421:
1204:
388:
359:
229:
8:
4193:
174:
2735:
4272:
3214:
2887:
2867:
2847:
2827:
2715:
2552:
2439:
2419:
2367:
2347:
2327:
2303:
2283:
2259:
2239:
2219:
2196:
2176:
2156:
2136:
2104:
2084:
2064:
2044:
2024:
2004:
1984:
1964:
1944:
1924:
1765:
1745:
1725:
659:
607:
467:
335:
315:
262:
977:
and their point set. It is done recursively until there is only one point in the set.
4303:
3986:
988:
denote the size of the longest interval of the bounding hyperrectangle of point set
4295:
4276:
4264:
4235:
155:, and is useful in approximating solutions to several problems pertaining to this.
4292:
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on
Discrete Algorithms
973:
is split along its longest side in two equal parts which form the two children of
4299:
152:
1530:
Visual representation of a well-separated pair computed with the bounding boxes
149:
4268:
4323:
438:
containing it, such that the two spheres have a minimum distance of at least
145:
1298:
is a hyperrectangle which each side has a length of zero. Store in
1035:
is a hyperrectangle which each side has a length of zero. Store in
4240:
4223:
1534:
The WSPD can be extracted from such a split tree by calling the recursive
4152:{\displaystyle O(n\lg n+(\epsilon ^{-2}\lg ^{2}{\frac {1}{\epsilon }})n)}
144:
The graph induced by a well-separated pair decomposition can serve as a
3941:
593:{\displaystyle (A_{1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})}
415:
4221:
2324:
on the children in one of the nodes of one of the subtrees of
464:
We consider a sequence of well-separated pairs of subsets of
4194:"The well-separated pair decomposition and its applications"
1008:. We give pseudocode for the Split tree computation below.
141:, there exists precisely one pair which separates the two.
1004:-th dimension of the bounding hyperrectangle of point set
943:
The general principle of the split tree of a point set
4222:
Callahan, P. B. & Kosaraju, S. R. (January 1995).
1201:
time below. The goal is to loop over the list in only
4079:
4043:
4002:
3950:
3910:
3869:
3824:
3773:
3728:
3518:
3404:
3311:
3274:
3237:
3217:
3185:
2954:
2910:
2890:
2870:
2850:
2830:
2810:
2763:
2738:
2718:
2638:
2612:
2575:
2555:
2523:
2473:
2442:
2422:
2390:
2370:
2350:
2330:
2306:
2286:
2262:
2242:
2222:
2199:
2179:
2159:
2139:
2107:
2087:
2067:
2047:
2027:
2007:
1987:
1967:
1947:
1927:
1898:
1872:
1846:
1820:
1788:
1768:
1748:
1728:
1207:
1169:
1130:
908:
869:
818:
785:
750:
717:
682:
662:
630:
610:
490:
470:
444:
424:
391:
362:
338:
318:
285:
265:
232:
203:
177:
115:
65:
30:
1918:. Assume without loss of generality that (i) holds.
4217:
4215:
4213:
1722:Now, we have to prove that for any distinct points
4254:
4151:
4061:
4026:
3974:
3928:
3893:
3848:
3803:
3752:
3699:
3500:
3382:
3297:
3260:
3223:
3203:
3166:
2938:
2896:
2876:
2856:
2836:
2816:
2796:
2749:
2724:
2698:
2624:
2598:
2561:
2541:
2498:
2448:
2428:
2408:
2376:
2356:
2336:
2312:
2292:
2268:
2248:
2228:
2205:
2185:
2165:
2145:
2113:
2093:
2073:
2053:
2033:
2013:
1993:
1973:
1953:
1933:
1910:
1884:
1858:
1832:
1806:
1774:
1754:
1734:
1275:be the hyperplane that splits the longest side of
1222:
1193:
1152:
932:
894:
837:
804:
769:
736:
700:
668:
648:
616:
592:
476:
453:
430:
406:
377:
344:
324:
297:
271:
247:
218:
189:
133:
97:
51:
2280:on the children of a higher node would result of
1163:We give a more efficient algorithm that runs in
1108:as, respectively, the left and right children of
4321:
4210:
1420:be respectively, the left and right children of
1279:in two. Here is the algorithm in pseudo-code:
4191:
2904:are in two well-separated sets, we have that
863:, it is possible to construct a WSPD of size
3198:
3186:
2536:
2524:
2403:
2391:
1801:
1789:
1692:-well-separated pairs from all the calls of
167:Visual representation of well-separated pair
3501:{\displaystyle |p'q'|\leq |p'p|+|pq|+|qq'|}
4289:
4239:
3211:be a well-separated pair with respect to
2824:is the radius of the enclosing circle of
2549:be a well-separated pair with respect to
206:
52:{\displaystyle S\subset \mathbb {R} ^{d}}
39:
1525:
602:well-separated pair decomposition (WSPD)
162:
22:well-separated pair decomposition (WSPD)
3396:: By the triangle inequality, we have:
951:of the tree represents a set of points
4322:
4187:
4185:
4183:
4181:
4179:
4177:
4175:
4173:
3383:{\displaystyle |p'q'|\leq (1+4/s)|pq|}
2384:not being in any pair. Thus, the pair
1708:Proof of correctness of the algorithm
1575:that is not a leaf in the split tree
4170:
2699:{\displaystyle |pp'|\leq (2/s)|pq|}
1617:are well-separated with respect to
1521:
109:, and for each two distinct points
13:
2757:are in the same set, we have that
2041:. Because of the last assumption,
197:be two disjoint sets of points in
14:
4341:
3992:Provide a t-approximation of the
2236:is the lowest common ancestor of
1941:be the lowest common ancestor of
257:axis-aligned minimum bounding box
59:, is a sequence of pairs of sets
4192:Smid, Michiel (16 August 2005).
2797:{\displaystyle |pp'|\leq 2\rho }
2320:not being in a pair and calling
1556:denote the children of the node
219:{\displaystyle \mathbb {R} ^{d}}
4071:Euclidean minimum spanning tree
3994:Euclidean minimum spanning tree
3709:
2939:{\displaystyle |pq|\geq s\rho }
1651:) Recursively call
1333:-th dimension be the one where
1051:-th dimension be the one where
849:
624:if for any two distinct points
4283:
4248:
4146:
4140:
4101:
4083:
4056:
4044:
4021:
4006:
3969:
3954:
3923:
3911:
3888:
3873:
3843:
3828:
3798:
3777:
3747:
3732:
3689:
3678:
3674:
3654:
3640:
3629:
3625:
3611:
3604:
3593:
3585:
3574:
3570:
3556:
3545:
3524:
3494:
3478:
3470:
3459:
3451:
3435:
3427:
3406:
3376:
3365:
3361:
3341:
3334:
3313:
3156:
3145:
3127:
3111:
3099:
3085:
3074:
3057:
3041:
3028:
3014:
3003:
2980:
2964:
2923:
2912:
2781:
2765:
2692:
2681:
2677:
2663:
2656:
2640:
2493:
2477:
1696:gives the WSPD for separation
1217:
1211:
1188:
1173:
1147:
1134:
927:
912:
889:
873:
587:
561:
549:
523:
517:
491:
401:
395:
372:
366:
242:
236:
92:
66:
1:
4163:
4062:{\displaystyle (1+\epsilon )}
3929:{\displaystyle (1-\epsilon )}
3861:all-nearest neighbors problem
2509:
2416:is the unique one separating
1560:. We give pseudocode for the
854:
701:{\displaystyle 1\leq i\leq m}
656:, there exists precisely one
158:
98:{\displaystyle (A_{i},B_{i})}
4300:10.1137/1.9781611974331.ch85
1542:node in the split tree. Let
1538:function on the children of
7:
3804:{\displaystyle O(n\lg n+k)}
1593:We give pseudocode for the
1259:is sorted according to the
10:
4346:
3767:-closest pairs problem in
1981:in the split tree and let
958:and that the bounding box
838:{\displaystyle p\in B_{i}}
805:{\displaystyle q\in A_{i}}
770:{\displaystyle q\in B_{i}}
737:{\displaystyle p\in A_{i}}
4269:10.1007/s00453-001-0114-7
4027:{\displaystyle O(n\lg n)}
3975:{\displaystyle O(n\lg n)}
3894:{\displaystyle O(n\lg n)}
3849:{\displaystyle O(n\lg n)}
3818:-closest pair problem in
3753:{\displaystyle O(n\lg n)}
3510:From Lemma 1, we obtain:
3298:{\displaystyle q,q'\in B}
3261:{\displaystyle p,p'\in A}
2599:{\displaystyle p,p'\in A}
2499:{\displaystyle O(s^{d}n)}
1782:, there is a unique pair
1194:{\displaystyle O(n\lg n)}
1039:the only point in S.
933:{\displaystyle O(n\lg n)}
895:{\displaystyle O(s^{d}n)}
859:By way of constructing a
105:, such that each pair is
1271:be the point. Also, let
1153:{\displaystyle O(n^{2})}
649:{\displaystyle p,q\in S}
134:{\displaystyle p,q\in S}
3204:{\displaystyle \{A,B\}}
2542:{\displaystyle \{A,B\}}
2409:{\displaystyle \{A,B\}}
2125:is necessarily done in
1807:{\displaystyle \{A,B\}}
1124:This algorithm runs in
1000:denote the size of the
4330:Computational geometry
4153:
4069:-approximation of the
4063:
4028:
3976:
3930:
3895:
3850:
3805:
3754:
3701:
3502:
3384:
3299:
3262:
3225:
3205:
3168:
2940:
2898:
2878:
2858:
2838:
2818:
2798:
2751:
2726:
2700:
2626:
2625:{\displaystyle q\in B}
2600:
2563:
2543:
2500:
2450:
2430:
2410:
2378:
2358:
2338:
2314:
2294:
2270:
2250:
2230:
2207:
2187:
2167:
2147:
2115:
2095:
2075:
2055:
2035:
2015:
1995:
1975:
1955:
1935:
1912:
1911:{\displaystyle q\in A}
1886:
1885:{\displaystyle p\in B}
1860:
1859:{\displaystyle q\in B}
1834:
1833:{\displaystyle p\in A}
1808:
1776:
1756:
1736:
1531:
1244:-th coordinate of the
1224:
1195:
1154:
934:
896:
839:
806:
771:
738:
702:
670:
650:
618:
594:
478:
455:
454:{\displaystyle s\rho }
432:
408:
379:
346:
326:
299:
298:{\displaystyle s>0}
273:
249:
220:
191:
168:
135:
99:
53:
18:computational geometry
4241:10.1145/200836.200853
4154:
4064:
4029:
3977:
3931:
3896:
3851:
3806:
3755:
3702:
3503:
3385:
3300:
3263:
3226:
3206:
3169:
2941:
2899:
2879:
2859:
2839:
2819:
2817:{\displaystyle \rho }
2799:
2752:
2727:
2701:
2627:
2601:
2564:
2544:
2501:
2451:
2431:
2411:
2379:
2359:
2339:
2315:
2295:
2271:
2251:
2231:
2208:
2188:
2168:
2148:
2116:
2096:
2076:
2061:is in the subtree of
2056:
2036:
2016:
1996:
1976:
1956:
1936:
1913:
1887:
1861:
1835:
1809:
1777:
1757:
1737:
1529:
1380:size := size - 1
1225:
1196:
1155:
1094:w := SplitTree(S
1087:v := SplitTree(S
935:
897:
840:
807:
772:
739:
703:
671:
651:
619:
595:
479:
456:
433:
431:{\displaystyle \rho }
409:
380:
347:
327:
300:
274:
250:
221:
192:
166:
136:
100:
54:
4077:
4041:
4000:
3948:
3908:
3867:
3822:
3771:
3726:
3720:closest pair problem
3516:
3402:
3309:
3272:
3235:
3215:
3183:
2952:
2908:
2888:
2868:
2848:
2828:
2808:
2761:
2736:
2716:
2636:
2610:
2573:
2553:
2521:
2471:
2440:
2420:
2388:
2368:
2348:
2328:
2304:
2284:
2260:
2240:
2220:
2197:
2177:
2157:
2137:
2105:
2085:
2065:
2045:
2025:
2005:
1985:
1965:
1945:
1925:
1896:
1870:
1844:
1818:
1786:
1766:
1746:
1726:
1600:FindPairs(v, w)
1223:{\displaystyle O(n)}
1205:
1167:
1128:
906:
867:
816:
783:
748:
715:
680:
660:
628:
608:
488:
468:
442:
422:
407:{\displaystyle R(B)}
389:
378:{\displaystyle R(A)}
360:
336:
316:
283:
263:
248:{\displaystyle R(X)}
230:
201:
175:
113:
63:
28:
4073:in d dimensions in
3996:in d dimensions in
2021:be the children of
1567:FindWSPD(T, s)
1263:-th coordinate and
708:, such that either
190:{\displaystyle A,B}
24:of a set of points
4228:Journal of the ACM
4149:
4059:
4024:
3985:Directly induce a
3972:
3944:of a point set in
3926:
3891:
3846:
3801:
3750:
3697:
3695:
3498:
3380:
3295:
3258:
3221:
3201:
3164:
3162:
2946:. We obtain that:
2936:
2894:
2874:
2854:
2834:
2814:
2794:
2750:{\displaystyle p'}
2747:
2722:
2696:
2622:
2596:
2559:
2539:
2496:
2446:
2426:
2406:
2374:
2354:
2334:
2310:
2290:
2266:
2246:
2226:
2203:
2183:
2163:
2143:
2133:leading to having
2111:
2101:in the subtree of
2091:
2071:
2051:
2031:
2011:
1991:
1971:
1951:
1931:
1908:
1882:
1856:
1830:
1804:
1772:
1752:
1732:
1532:
1405:}
1393:}
1302:the only point in
1220:
1191:
1150:
947:is that each node
930:
892:
835:
802:
767:
734:
698:
666:
646:
614:
590:
474:
451:
428:
404:
375:
342:
322:
295:
269:
259:for the points in
245:
216:
187:
169:
131:
95:
49:
4309:978-1-61197-433-1
4138:
3224:{\displaystyle s}
3142:
3093:
3065:
3022:
2988:
2897:{\displaystyle q}
2877:{\displaystyle p}
2857:{\displaystyle B}
2837:{\displaystyle A}
2725:{\displaystyle p}
2562:{\displaystyle s}
2461:
2460:
2449:{\displaystyle q}
2429:{\displaystyle p}
2377:{\displaystyle q}
2357:{\displaystyle p}
2337:{\displaystyle u}
2313:{\displaystyle q}
2293:{\displaystyle p}
2269:{\displaystyle q}
2249:{\displaystyle p}
2229:{\displaystyle u}
2206:{\displaystyle B}
2186:{\displaystyle q}
2166:{\displaystyle A}
2146:{\displaystyle p}
2114:{\displaystyle w}
2094:{\displaystyle q}
2074:{\displaystyle v}
2054:{\displaystyle p}
2034:{\displaystyle u}
2014:{\displaystyle w}
1994:{\displaystyle v}
1974:{\displaystyle q}
1954:{\displaystyle p}
1934:{\displaystyle u}
1775:{\displaystyle S}
1755:{\displaystyle q}
1735:{\displaystyle p}
1670:Recursively call
1321:R(u) := R(S)
1292:R(u) := R(S)
1114:R(u) := R(S)
1029:R(u) := R(S)
669:{\displaystyle i}
617:{\displaystyle S}
477:{\displaystyle S}
356:, if for each of
345:{\displaystyle B}
325:{\displaystyle A}
307:separation factor
272:{\displaystyle X}
4337:
4314:
4313:
4287:
4281:
4280:
4252:
4246:
4245:
4243:
4219:
4208:
4207:
4205:
4203:
4198:
4189:
4158:
4156:
4155:
4150:
4139:
4131:
4126:
4125:
4116:
4115:
4068:
4066:
4065:
4060:
4033:
4031:
4030:
4025:
3981:
3979:
3978:
3973:
3935:
3933:
3932:
3927:
3900:
3898:
3897:
3892:
3855:
3853:
3852:
3847:
3810:
3808:
3807:
3802:
3759:
3757:
3756:
3751:
3706:
3704:
3703:
3698:
3696:
3692:
3681:
3670:
3647:
3643:
3632:
3621:
3607:
3596:
3588:
3577:
3566:
3548:
3543:
3535:
3527:
3507:
3505:
3504:
3499:
3497:
3492:
3481:
3473:
3462:
3454:
3446:
3438:
3430:
3425:
3417:
3409:
3389:
3387:
3386:
3381:
3379:
3368:
3357:
3337:
3332:
3324:
3316:
3304:
3302:
3301:
3296:
3288:
3267:
3265:
3264:
3259:
3251:
3230:
3228:
3227:
3222:
3210:
3208:
3207:
3202:
3173:
3171:
3170:
3165:
3163:
3159:
3148:
3143:
3135:
3130:
3125:
3114:
3106:
3103:
3094:
3089:
3088:
3077:
3071:
3066:
3061:
3060:
3055:
3044:
3038:
3035:
3032:
3023:
3018:
3017:
3006:
3000:
2989:
2984:
2983:
2978:
2967:
2961:
2958:
2945:
2943:
2942:
2937:
2926:
2915:
2903:
2901:
2900:
2895:
2883:
2881:
2880:
2875:
2863:
2861:
2860:
2855:
2843:
2841:
2840:
2835:
2823:
2821:
2820:
2815:
2803:
2801:
2800:
2795:
2784:
2779:
2768:
2756:
2754:
2753:
2748:
2746:
2731:
2729:
2728:
2723:
2705:
2703:
2702:
2697:
2695:
2684:
2673:
2659:
2654:
2643:
2631:
2629:
2628:
2623:
2605:
2603:
2602:
2597:
2589:
2568:
2566:
2565:
2560:
2548:
2546:
2545:
2540:
2505:
2503:
2502:
2497:
2489:
2488:
2455:
2453:
2452:
2447:
2435:
2433:
2432:
2427:
2415:
2413:
2412:
2407:
2383:
2381:
2380:
2375:
2363:
2361:
2360:
2355:
2344:would result by
2343:
2341:
2340:
2335:
2323:
2319:
2317:
2316:
2311:
2299:
2297:
2296:
2291:
2279:
2275:
2273:
2272:
2267:
2255:
2253:
2252:
2247:
2235:
2233:
2232:
2227:
2212:
2210:
2209:
2204:
2192:
2190:
2189:
2184:
2172:
2170:
2169:
2164:
2152:
2150:
2149:
2144:
2132:
2128:
2124:
2120:
2118:
2117:
2112:
2100:
2098:
2097:
2092:
2080:
2078:
2077:
2072:
2060:
2058:
2057:
2052:
2040:
2038:
2037:
2032:
2020:
2018:
2017:
2012:
2000:
1998:
1997:
1992:
1980:
1978:
1977:
1972:
1960:
1958:
1957:
1952:
1940:
1938:
1937:
1932:
1917:
1915:
1914:
1909:
1891:
1889:
1888:
1883:
1865:
1863:
1862:
1857:
1839:
1837:
1836:
1831:
1813:
1811:
1810:
1805:
1781:
1779:
1778:
1773:
1761:
1759:
1758:
1753:
1741:
1739:
1738:
1733:
1718:
1704:
1703:
1699:
1695:
1691:
1685:
1677:
1666:
1658:
1650:
1632:
1620:
1616:
1609:
1597:function below.
1596:
1564:function below.
1563:
1559:
1555:
1548:
1537:
1522:WSPD computation
1514:
1511:
1510:
1509:
1505:
1496:
1489:
1483:
1480:
1470:
1460:
1453:
1447:
1444:
1434:
1423:
1419:
1415:
1411:
1408:
1404:
1392:
1381:
1378:
1368:
1358:
1351:
1344:
1328:
1325:
1322:
1319:
1312:
1311:size := |S|
1305:
1301:
1297:
1293:
1290:
1284:
1278:
1274:
1270:
1258:
1251:
1239:
1229:
1227:
1226:
1221:
1200:
1198:
1197:
1192:
1159:
1157:
1156:
1151:
1146:
1145:
1121:
1115:
1111:
1107:
1103:
1099:
1092:
1084:
1077:
1066:
1062:
1046:
1038:
1034:
1030:
1027:
1021:
1018:be the node for
1017:
1013:
1007:
999:
991:
987:
976:
972:
965:
957:
950:
946:
939:
937:
936:
931:
901:
899:
898:
893:
885:
884:
844:
842:
841:
836:
834:
833:
811:
809:
808:
803:
801:
800:
776:
774:
773:
768:
766:
765:
743:
741:
740:
735:
733:
732:
707:
705:
704:
699:
675:
673:
672:
667:
655:
653:
652:
647:
623:
621:
620:
615:
599:
597:
596:
591:
586:
585:
573:
572:
548:
547:
535:
534:
516:
515:
503:
502:
483:
481:
480:
475:
460:
458:
457:
452:
437:
435:
434:
429:
413:
411:
410:
405:
384:
382:
381:
376:
351:
349:
348:
343:
331:
329:
328:
323:
304:
302:
301:
296:
278:
276:
275:
270:
254:
252:
251:
246:
225:
223:
222:
217:
215:
214:
209:
196:
194:
193:
188:
140:
138:
137:
132:
104:
102:
101:
96:
91:
90:
78:
77:
58:
56:
55:
50:
48:
47:
42:
4345:
4344:
4340:
4339:
4338:
4336:
4335:
4334:
4320:
4319:
4318:
4317:
4310:
4288:
4284:
4253:
4249:
4220:
4211:
4201:
4199:
4196:
4190:
4171:
4166:
4130:
4121:
4117:
4108:
4104:
4078:
4075:
4074:
4042:
4039:
4038:
4001:
3998:
3997:
3989:of a point set.
3949:
3946:
3945:
3909:
3906:
3905:
3868:
3865:
3864:
3823:
3820:
3819:
3772:
3769:
3768:
3727:
3724:
3723:
3712:
3694:
3693:
3688:
3677:
3666:
3645:
3644:
3639:
3628:
3617:
3603:
3592:
3584:
3573:
3562:
3549:
3544:
3536:
3528:
3523:
3519:
3517:
3514:
3513:
3493:
3485:
3477:
3469:
3458:
3450:
3439:
3434:
3426:
3418:
3410:
3405:
3403:
3400:
3399:
3375:
3364:
3353:
3333:
3325:
3317:
3312:
3310:
3307:
3306:
3281:
3273:
3270:
3269:
3244:
3236:
3233:
3232:
3216:
3213:
3212:
3184:
3181:
3180:
3161:
3160:
3155:
3144:
3134:
3126:
3118:
3110:
3104:
3102:
3096:
3095:
3084:
3073:
3072:
3070:
3056:
3048:
3040:
3039:
3037:
3033:
3031:
3025:
3024:
3013:
3002:
3001:
2999:
2979:
2971:
2963:
2962:
2960:
2955:
2953:
2950:
2949:
2922:
2911:
2909:
2906:
2905:
2889:
2886:
2885:
2869:
2866:
2865:
2849:
2846:
2845:
2829:
2826:
2825:
2809:
2806:
2805:
2780:
2772:
2764:
2762:
2759:
2758:
2739:
2737:
2734:
2733:
2717:
2714:
2713:
2691:
2680:
2669:
2655:
2647:
2639:
2637:
2634:
2633:
2611:
2608:
2607:
2582:
2574:
2571:
2570:
2554:
2551:
2550:
2522:
2519:
2518:
2512:
2484:
2480:
2472:
2469:
2468:
2462:
2441:
2438:
2437:
2421:
2418:
2417:
2389:
2386:
2385:
2369:
2366:
2365:
2349:
2346:
2345:
2329:
2326:
2325:
2321:
2305:
2302:
2301:
2285:
2282:
2281:
2277:
2261:
2258:
2257:
2241:
2238:
2237:
2221:
2218:
2217:
2198:
2195:
2194:
2178:
2175:
2174:
2158:
2155:
2154:
2138:
2135:
2134:
2130:
2126:
2122:
2106:
2103:
2102:
2086:
2083:
2082:
2066:
2063:
2062:
2046:
2043:
2042:
2026:
2023:
2022:
2006:
2003:
2002:
1986:
1983:
1982:
1966:
1963:
1962:
1946:
1943:
1942:
1926:
1923:
1922:
1897:
1894:
1893:
1871:
1868:
1867:
1845:
1842:
1841:
1819:
1816:
1815:
1787:
1784:
1783:
1767:
1764:
1763:
1747:
1744:
1743:
1727:
1724:
1723:
1716:
1709:
1697:
1693:
1689:
1686:
1683:
1679:
1675:
1671:
1664:
1660:
1656:
1652:
1648:
1644:
1640:
1630:
1626:
1622:
1618:
1615:
1611:
1608:
1604:
1595:FindPairs(v, w)
1594:
1591:
1589:
1585:
1561:
1557:
1554:
1550:
1547:
1543:
1535:
1524:
1515:
1512:
1507:
1503:
1502:
1500:
1494:
1490:
1488:
1484:
1481:
1479:
1475:
1471:
1468:
1464:
1458:
1454:
1452:
1448:
1445:
1443:
1439:
1435:
1432:
1428:
1421:
1417:
1413:
1410:k := k - 1
1409:
1407:j := j + 1
1406:
1402:
1398:
1394:
1390:
1386:
1382:
1379:
1376:
1372:
1366:
1362:
1356:
1352:
1349:
1345:
1342:
1338:
1334:
1326:
1323:
1320:
1317:
1310:
1303:
1299:
1295:
1291:
1288:
1283:SplitTree(S, u)
1282:
1276:
1272:
1268:
1264:
1257:
1253:
1249:
1238:
1234:
1206:
1203:
1202:
1168:
1165:
1164:
1141:
1137:
1129:
1126:
1125:
1122:
1119:
1113:
1109:
1105:
1101:
1097:
1093:
1090:
1086:
1083:
1079:
1076:
1072:
1064:
1060:
1056:
1052:
1044:
1036:
1032:
1028:
1025:
1019:
1015:
1011:
1005:
997:
993:
989:
985:
981:
974:
971:
967:
963:
959:
956:
952:
948:
944:
907:
904:
903:
880:
876:
868:
865:
864:
861:fair split tree
857:
852:
829:
825:
817:
814:
813:
796:
792:
784:
781:
780:
761:
757:
749:
746:
745:
728:
724:
716:
713:
712:
681:
678:
677:
661:
658:
657:
629:
626:
625:
609:
606:
605:
581:
577:
568:
564:
543:
539:
530:
526:
511:
507:
498:
494:
489:
486:
485:
469:
466:
465:
443:
440:
439:
423:
420:
419:
414:there exists a
390:
387:
386:
361:
358:
357:
337:
334:
333:
317:
314:
313:
284:
281:
280:
264:
261:
260:
231:
228:
227:
210:
205:
204:
202:
199:
198:
176:
173:
172:
161:
153:Euclidean graph
114:
111:
110:
86:
82:
73:
69:
64:
61:
60:
43:
38:
37:
29:
26:
25:
12:
11:
5:
4343:
4333:
4332:
4316:
4315:
4308:
4282:
4263:(2): 263–269.
4247:
4209:
4168:
4167:
4165:
4162:
4161:
4160:
4148:
4145:
4142:
4137:
4134:
4129:
4124:
4120:
4114:
4111:
4107:
4103:
4100:
4097:
4094:
4091:
4088:
4085:
4082:
4058:
4055:
4052:
4049:
4046:
4035:
4023:
4020:
4017:
4014:
4011:
4008:
4005:
3990:
3983:
3971:
3968:
3965:
3962:
3959:
3956:
3953:
3925:
3922:
3919:
3916:
3913:
3902:
3890:
3887:
3884:
3881:
3878:
3875:
3872:
3857:
3845:
3842:
3839:
3836:
3833:
3830:
3827:
3812:
3800:
3797:
3794:
3791:
3788:
3785:
3782:
3779:
3776:
3761:
3749:
3746:
3743:
3740:
3737:
3734:
3731:
3711:
3708:
3691:
3687:
3684:
3680:
3676:
3673:
3669:
3665:
3662:
3659:
3656:
3653:
3650:
3648:
3646:
3642:
3638:
3635:
3631:
3627:
3624:
3620:
3616:
3613:
3610:
3606:
3602:
3599:
3595:
3591:
3587:
3583:
3580:
3576:
3572:
3569:
3565:
3561:
3558:
3555:
3552:
3550:
3547:
3542:
3539:
3534:
3531:
3526:
3522:
3521:
3496:
3491:
3488:
3484:
3480:
3476:
3472:
3468:
3465:
3461:
3457:
3453:
3449:
3445:
3442:
3437:
3433:
3429:
3424:
3421:
3416:
3413:
3408:
3378:
3374:
3371:
3367:
3363:
3360:
3356:
3352:
3349:
3346:
3343:
3340:
3336:
3331:
3328:
3323:
3320:
3315:
3294:
3291:
3287:
3284:
3280:
3277:
3257:
3254:
3250:
3247:
3243:
3240:
3220:
3200:
3197:
3194:
3191:
3188:
3158:
3154:
3151:
3147:
3141:
3138:
3133:
3129:
3124:
3121:
3117:
3113:
3109:
3107:
3105:
3101:
3098:
3097:
3092:
3087:
3083:
3080:
3076:
3069:
3064:
3059:
3054:
3051:
3047:
3043:
3036:
3034:
3030:
3027:
3026:
3021:
3016:
3012:
3009:
3005:
2998:
2995:
2992:
2987:
2982:
2977:
2974:
2970:
2966:
2959:
2957:
2935:
2932:
2929:
2925:
2921:
2918:
2914:
2893:
2873:
2853:
2833:
2813:
2793:
2790:
2787:
2783:
2778:
2775:
2771:
2767:
2745:
2742:
2721:
2694:
2690:
2687:
2683:
2679:
2676:
2672:
2668:
2665:
2662:
2658:
2653:
2650:
2646:
2642:
2621:
2618:
2615:
2595:
2592:
2588:
2585:
2581:
2578:
2558:
2538:
2535:
2532:
2529:
2526:
2511:
2508:
2495:
2492:
2487:
2483:
2479:
2476:
2459:
2458:
2445:
2425:
2405:
2402:
2399:
2396:
2393:
2373:
2353:
2333:
2309:
2289:
2265:
2245:
2225:
2202:
2182:
2162:
2142:
2123:FindPairs(v,w)
2110:
2090:
2070:
2050:
2030:
2010:
1990:
1970:
1950:
1930:
1907:
1904:
1901:
1881:
1878:
1875:
1855:
1852:
1849:
1829:
1826:
1823:
1803:
1800:
1797:
1794:
1791:
1771:
1751:
1731:
1711:
1710:
1707:
1702:
1694:FindPairs(v,w)
1688:Combining the
1681:
1673:
1662:
1661:FindPairs(v, w
1654:
1653:FindPairs(v, w
1646:
1642:
1628:
1624:
1613:
1606:
1599:
1587:
1583:
1566:
1562:FindWSPD(T, s)
1552:
1545:
1536:FindPairs(v,w)
1523:
1520:
1513:SplitTree(S,u)
1492:
1486:
1477:
1476: := S \ S
1473:
1466:
1456:
1450:
1441:
1440: := S \ S
1437:
1430:
1424:.
1400:
1396:
1388:
1384:
1374:
1364:
1354:
1347:
1340:
1336:
1327:k : = |S|
1281:
1266:
1255:
1236:
1219:
1216:
1213:
1210:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1149:
1144:
1140:
1136:
1133:
1095:
1088:
1081:
1074:
1058:
1054:
1010:
995:
983:
969:
961:
954:
929:
926:
923:
920:
917:
914:
911:
891:
888:
883:
879:
875:
872:
856:
853:
851:
848:
847:
846:
832:
828:
824:
821:
799:
795:
791:
788:
778:
764:
760:
756:
753:
731:
727:
723:
720:
697:
694:
691:
688:
685:
665:
645:
642:
639:
636:
633:
613:
589:
584:
580:
576:
571:
567:
563:
560:
557:
554:
551:
546:
542:
538:
533:
529:
525:
522:
519:
514:
510:
506:
501:
497:
493:
473:
450:
447:
427:
403:
400:
397:
394:
374:
371:
368:
365:
354:well-separated
341:
321:
294:
291:
288:
268:
244:
241:
238:
235:
213:
208:
186:
183:
180:
160:
157:
130:
127:
124:
121:
118:
107:well-separated
94:
89:
85:
81:
76:
72:
68:
46:
41:
36:
33:
9:
6:
4:
3:
2:
4342:
4331:
4328:
4327:
4325:
4311:
4305:
4301:
4297:
4294:: 1220–1233.
4293:
4286:
4278:
4274:
4270:
4266:
4262:
4258:
4251:
4242:
4237:
4233:
4229:
4225:
4218:
4216:
4214:
4195:
4188:
4186:
4184:
4182:
4180:
4178:
4176:
4174:
4169:
4143:
4135:
4132:
4127:
4122:
4118:
4112:
4109:
4105:
4098:
4095:
4092:
4089:
4086:
4080:
4072:
4053:
4050:
4047:
4036:
4018:
4015:
4012:
4009:
4003:
3995:
3991:
3988:
3984:
3966:
3963:
3960:
3957:
3951:
3943:
3939:
3938:approximation
3920:
3917:
3914:
3903:
3885:
3882:
3879:
3876:
3870:
3862:
3858:
3840:
3837:
3834:
3831:
3825:
3817:
3813:
3795:
3792:
3789:
3786:
3783:
3780:
3774:
3766:
3762:
3744:
3741:
3738:
3735:
3729:
3721:
3717:
3716:
3715:
3707:
3685:
3682:
3671:
3667:
3663:
3660:
3657:
3651:
3649:
3636:
3633:
3622:
3618:
3614:
3608:
3600:
3597:
3589:
3581:
3578:
3567:
3563:
3559:
3553:
3551:
3540:
3537:
3532:
3529:
3511:
3508:
3489:
3486:
3482:
3474:
3466:
3463:
3455:
3447:
3443:
3440:
3431:
3422:
3419:
3414:
3411:
3397:
3395:
3391:
3372:
3369:
3358:
3354:
3350:
3347:
3344:
3338:
3329:
3326:
3321:
3318:
3292:
3289:
3285:
3282:
3278:
3275:
3255:
3252:
3248:
3245:
3241:
3238:
3218:
3195:
3192:
3189:
3178:
3174:
3152:
3149:
3139:
3136:
3131:
3122:
3119:
3115:
3108:
3090:
3081:
3078:
3067:
3062:
3052:
3049:
3045:
3019:
3010:
3007:
2996:
2993:
2990:
2985:
2975:
2972:
2968:
2947:
2933:
2930:
2927:
2919:
2916:
2891:
2871:
2851:
2831:
2811:
2791:
2788:
2785:
2776:
2773:
2769:
2743:
2740:
2719:
2711:
2707:
2688:
2685:
2674:
2670:
2666:
2660:
2651:
2648:
2644:
2619:
2616:
2613:
2593:
2590:
2586:
2583:
2579:
2576:
2556:
2533:
2530:
2527:
2516:
2507:
2490:
2485:
2481:
2474:
2465:
2457:
2443:
2423:
2400:
2397:
2394:
2371:
2351:
2331:
2307:
2287:
2263:
2243:
2223:
2214:
2200:
2180:
2160:
2140:
2108:
2088:
2068:
2048:
2028:
2008:
1988:
1968:
1948:
1928:
1919:
1905:
1902:
1899:
1879:
1876:
1873:
1853:
1850:
1847:
1827:
1824:
1821:
1798:
1795:
1792:
1769:
1749:
1729:
1720:
1713:
1712:
1706:
1705:
1701:
1669:
1638:
1635:
1603:
1598:
1581:
1578:
1574:
1570:
1565:
1541:
1528:
1519:
1499:
1463:
1427:
1371:
1361:
1332:
1315:
1309:
1287:
1280:
1262:
1248:-th point in
1247:
1243:
1231:
1214:
1208:
1185:
1182:
1179:
1176:
1170:
1161:
1142:
1138:
1131:
1118:
1070:
1050:
1042:
1024:
1009:
1003:
978:
941:
924:
921:
918:
915:
909:
886:
881:
877:
870:
862:
830:
826:
822:
819:
797:
793:
789:
786:
779:
762:
758:
754:
751:
729:
725:
721:
718:
711:
710:
709:
695:
692:
689:
686:
683:
663:
643:
640:
637:
634:
631:
611:
603:
582:
578:
574:
569:
565:
558:
555:
552:
544:
540:
536:
531:
527:
520:
512:
508:
504:
499:
495:
471:
462:
448:
445:
425:
417:
398:
392:
369:
363:
355:
339:
319:
310:
308:
292:
289:
286:
266:
258:
239:
233:
211:
184:
181:
178:
165:
156:
154:
151:
147:
142:
128:
125:
122:
119:
116:
108:
87:
83:
79:
74:
70:
44:
34:
31:
23:
19:
4291:
4285:
4260:
4257:Algorithmica
4256:
4250:
4234:(1): 67–90.
4231:
4227:
4200:. Retrieved
3815:
3764:
3713:
3710:Applications
3512:
3509:
3398:
3393:
3392:
3176:
3175:
2948:
2709:
2708:
2514:
2513:
2466:
2463:
2215:
2121:. A call to
1920:
1814:so that (i)
1721:
1714:
1687:
1667:
1636:
1633:
1601:
1592:
1579:
1576:
1572:
1568:
1539:
1533:
1516:
1497:
1469:< h(R(S))
1461:
1433:> h(R(S))
1425:
1377:> h(R(S))
1369:
1367:< h(R(S))
1359:
1330:
1324:j : = 1
1313:
1307:
1285:
1260:
1245:
1241:
1232:
1162:
1123:
1116:
1068:
1048:
1040:
1022:
1012:SplitTree(S)
1001:
979:
942:
858:
850:Construction
601:
463:
353:
312:We consider
311:
306:
170:
143:
106:
21:
15:
1680:FindPairs(v
1672:FindPairs(v
1582:FindPairs(u
1491:SplitTree(S
1485:S := S
1482:u := v
1455:SplitTree(S
1449:S := S
1446:u := w
1403:∪ {p(S_i^k)
1399: : = S
1391:∪ {p(S_i^j)
1387: : = S
1357: : = ∅
1350: : = ∅
305:denote the
255:denote the
4164:References
4037:Provide a
3904:Provide a
3859:Solve the
3814:Solve the
3763:Solve the
3718:Solve the
2864:. Because
2712:: Because
2510:Properties
2276:, calling
1645:(R(v)) ≤ L
1339:(R(S)) = L
1252:such that
1112:.
1085:.
1067:along the
1057:(R(S)) = L
855:Split tree
418:of radius
159:Definition
4136:ϵ
4128:
4110:−
4106:ϵ
4093:
4054:ϵ
4016:
3987:t-spanner
3964:
3921:ϵ
3918:−
3883:
3838:
3787:
3742:
3554:≤
3432:≤
3339:≤
3290:∈
3253:∈
3132:≤
3100:⇔
3068:≤
3029:⇔
2997:≤
2994:ρ
2991:≤
2934:ρ
2928:≥
2812:ρ
2792:ρ
2786:≤
2661:≤
2617:∈
2591:∈
2322:FindPairs
2278:FindPairs
2131:FindPairs
1903:∈
1877:∈
1851:∈
1825:∈
1717:FindPairs
1183:
922:
823:∈
790:∈
755:∈
722:∈
693:≤
687:≤
641:∈
556:…
449:ρ
426:ρ
146:k-spanner
126:∈
35:⊂
4324:Category
4202:26 March
3942:diameter
3541:′
3533:′
3490:′
3444:′
3423:′
3415:′
3330:′
3322:′
3305:. Then,
3286:′
3249:′
3123:′
3053:′
2976:′
2777:′
2744:′
2652:′
2632:. Then,
2587:′
2216:Because
2127:FindWSPD
1866:or (ii)
1569:for each
1329:Let the
1316:Compute
1047:Let the
1043:Compute
992:and let
600:to be a
150:complete
4277:9758120
3940:of the
3177:Lemma 2
2515:Lemma 1
1621:report
1506:⁄
1501:size ≤
1462:else if
1289:|S| = 1
1273:h(R(S))
1240:be the
1026:|S| = 1
148:of the
4306:
4275:
3231:. Let
3179:: Let
2804:where
2569:. Let
2517:: Let
1649:(R(w))
1623:pair(S
1343:(R(S))
1314:repeat
1306:.
1160:time.
1117:return
1100:Store
1063:Split
1061:(R(S))
998:(R(X))
986:(R(X))
940:time.
416:d-ball
352:to be
279:, and
4273:S2CID
4197:(PDF)
4159:time.
4034:time.
3982:time.
3901:time.
3856:time.
3811:time.
3760:time.
3394:Proof
2710:Proof
1571:node
1540:every
1498:until
1360:while
4304:ISBN
4204:2014
3268:and
2884:and
2844:and
2732:and
2606:and
2436:and
2300:and
2256:and
2173:and
2081:and
2001:and
1961:and
1921:Let
1892:and
1840:and
1742:and
1684:, w)
1678:and
1676:, w)
1668:else
1659:and
1634:else
1610:and
1416:and
1412:Let
1318:R(S)
1308:else
1296:R(S)
1277:R(S)
1233:Let
1104:and
1078:and
1065:R(S)
1045:R(S)
1041:else
1033:R(S)
1014:Let
980:Let
812:and
777:, or
744:and
385:and
332:and
290:>
171:Let
20:, a
4296:doi
4265:doi
4236:doi
3863:in
3722:in
2364:or
2193:in
2153:in
1762:in
1647:max
1643:max
1627:, S
1586:, u
1495:,w)
1459:,v)
1370:and
1337:max
1294://
1265:p(S
1055:max
1031://
984:max
966:of
960:R(S
902:in
604:of
16:In
4326::
4302:.
4271:.
4261:33
4259:.
4232:42
4230:.
4226:.
4212:^
4172:^
4119:lg
4090:lg
4013:lg
3961:lg
3880:lg
3835:lg
3784:lg
3739:lg
3390:.
2706:.
2506:.
2456:.
2213:.
1719:.
1700:.
1639:(
1637:if
1602:if
1590:)
1580:do
1549:/
1426:if
1286:if
1180:lg
1023:if
919:lg
676:,
484:,
461:.
309:.
226:,
4312:.
4298::
4279:.
4267::
4244:.
4238::
4206:.
4147:)
4144:n
4141:)
4133:1
4123:2
4113:2
4102:(
4099:+
4096:n
4087:n
4084:(
4081:O
4057:)
4051:+
4048:1
4045:(
4022:)
4019:n
4010:n
4007:(
4004:O
3970:)
3967:n
3958:n
3955:(
3952:O
3936:-
3924:)
3915:1
3912:(
3889:)
3886:n
3877:n
3874:(
3871:O
3844:)
3841:n
3832:n
3829:(
3826:O
3816:k
3799:)
3796:k
3793:+
3790:n
3781:n
3778:(
3775:O
3765:k
3748:)
3745:n
3736:n
3733:(
3730:O
3690:|
3686:q
3683:p
3679:|
3675:)
3672:s
3668:/
3664:4
3661:+
3658:1
3655:(
3652:=
3641:|
3637:q
3634:p
3630:|
3626:)
3623:s
3619:/
3615:2
3612:(
3609:+
3605:|
3601:q
3598:p
3594:|
3590:+
3586:|
3582:q
3579:p
3575:|
3571:)
3568:s
3564:/
3560:2
3557:(
3546:|
3538:q
3530:p
3525:|
3495:|
3487:q
3483:q
3479:|
3475:+
3471:|
3467:q
3464:p
3460:|
3456:+
3452:|
3448:p
3441:p
3436:|
3428:|
3420:q
3412:p
3407:|
3377:|
3373:q
3370:p
3366:|
3362:)
3359:s
3355:/
3351:4
3348:+
3345:1
3342:(
3335:|
3327:q
3319:p
3314:|
3293:B
3283:q
3279:,
3276:q
3256:A
3246:p
3242:,
3239:p
3219:s
3199:}
3196:B
3193:,
3190:A
3187:{
3157:|
3153:q
3150:p
3146:|
3140:s
3137:2
3128:|
3120:p
3116:p
3112:|
3091:s
3086:|
3082:q
3079:p
3075:|
3063:2
3058:|
3050:p
3046:p
3042:|
3020:s
3015:|
3011:q
3008:p
3004:|
2986:2
2981:|
2973:p
2969:p
2965:|
2931:s
2924:|
2920:q
2917:p
2913:|
2892:q
2872:p
2852:B
2832:A
2789:2
2782:|
2774:p
2770:p
2766:|
2741:p
2720:p
2693:|
2689:q
2686:p
2682:|
2678:)
2675:s
2671:/
2667:2
2664:(
2657:|
2649:p
2645:p
2641:|
2620:B
2614:q
2594:A
2584:p
2580:,
2577:p
2557:s
2537:}
2534:B
2531:,
2528:A
2525:{
2494:)
2491:n
2486:d
2482:s
2478:(
2475:O
2444:q
2424:p
2404:}
2401:B
2398:,
2395:A
2392:{
2372:q
2352:p
2332:u
2308:q
2288:p
2264:q
2244:p
2224:u
2201:B
2181:q
2161:A
2141:p
2109:w
2089:q
2069:v
2049:p
2029:u
2009:w
1989:v
1969:q
1949:p
1929:u
1906:A
1900:q
1880:B
1874:p
1854:B
1848:q
1828:A
1822:p
1802:}
1799:B
1796:,
1793:A
1790:{
1770:S
1750:q
1730:p
1698:s
1690:s
1682:r
1674:l
1665:)
1663:r
1657:)
1655:l
1641:L
1631:)
1629:w
1625:v
1619:s
1614:w
1612:S
1607:v
1605:S
1588:r
1584:l
1577:T
1573:u
1558:u
1553:r
1551:u
1546:l
1544:u
1508:2
1504:n
1493:w
1487:v
1478:w
1474:v
1472:S
1467:i
1465:S
1457:v
1451:w
1442:v
1438:w
1436:S
1431:i
1429:S
1422:u
1418:w
1414:v
1401:w
1397:w
1395:S
1389:v
1385:v
1383:S
1375:i
1373:S
1365:i
1363:S
1355:w
1353:S
1348:v
1346:S
1341:i
1335:L
1331:i
1304:S
1300:u
1269:)
1267:i
1261:i
1256:i
1254:S
1250:S
1246:j
1242:i
1237:i
1235:S
1218:)
1215:n
1212:(
1209:O
1189:)
1186:n
1177:n
1174:(
1171:O
1148:)
1143:2
1139:n
1135:(
1132:O
1120:u
1110:u
1106:w
1102:v
1098:)
1096:w
1091:)
1089:v
1082:w
1080:S
1075:v
1073:S
1069:i
1059:i
1053:L
1049:i
1037:u
1020:S
1016:u
1006:X
1002:i
996:i
994:L
990:X
982:L
975:u
970:u
968:S
964:)
962:u
955:u
953:S
949:u
945:S
928:)
925:n
916:n
913:(
910:O
890:)
887:n
882:d
878:s
874:(
871:O
845:.
831:i
827:B
820:p
798:i
794:A
787:q
763:i
759:B
752:q
730:i
726:A
719:p
696:m
690:i
684:1
664:i
644:S
638:q
635:,
632:p
612:S
588:)
583:m
579:B
575:,
570:m
566:A
562:(
559:,
553:,
550:)
545:2
541:B
537:,
532:2
528:A
524:(
521:,
518:)
513:1
509:B
505:,
500:1
496:A
492:(
472:S
446:s
402:)
399:B
396:(
393:R
373:)
370:A
367:(
364:R
340:B
320:A
293:0
287:s
267:X
243:)
240:X
237:(
234:R
212:d
207:R
185:B
182:,
179:A
129:S
123:q
120:,
117:p
93:)
88:i
84:B
80:,
75:i
71:A
67:(
45:d
40:R
32:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
