448:
485:
353:
2676:
2800:
using a divide-and-conquer algorithm. Start with a quadtree cell that contains all objects. Then recursively divide it to smaller quadtree cells, find the maximum in each smaller cell, and combine the results to get the maximum in the larger cell. Since the number of disjoint fat objects intersecting
3764:
2312:
Gálvez, Khan, Mari, Mömke, Pittu, and Wiese presented an algorithm partitioning the plane into a more general class of polygons. This simplifies the analysis and improves the approximation to 6-factor. Additionally, they improved the approximation to 3-factor and then to
4267:
is a set of objects in which the boundaries of every pair of objects intersect at most twice (Note that this definition relates to a whole collection, and does not say anything about the shapes of the specific objects in the collection). A pseudo-disks-set has a bounded
539:
The main challenge with this approach is to find a geometric way to divide the set into subsets. This may require to discard a small number of shapes that do not fit into any one of the subsets, as explained in the following subsections.
4181:
2601:
3596:
3607:
2257:
For a long time, it was not known whether a constant-factor approximation exists for axis-parallel rectangles of different lengths and heights. It was conjectured that such an approximation could be found using
4272:, i.e., the number of intersection points on the boundary of the union of all objects is linear in the number of objects. For example, a set of squares or circles of arbitrary sizes is a pseudo-disks-set.
3115:
theorem. A geometric separator is a line or shape that separates a given set of shapes to two smaller subsets, such that the number of shapes lost during the division is relatively small. This allows both
3056:
2048:
1944:
1717:
4366:
5287:
Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Reddy, Madhusudhan; Wiese, Andreas (2021-09-26). "A (2+\epsilon)-Approximation
Algorithm for Maximum Independent Set of Rectangles".
3482:
439:
In contrast to the 1-dimensional case, in 2 or more dimensions the MDS problem becomes NP-complete, and thus has either exact super-polynomial algorithms or approximate polynomial algorithms.
4248:
336:
4752:
2147:
1051:
912:
864:
4021:
3900:
3823:
1870:
1652:
1573:
1532:
1404:
1290:
1211:
466:
coordinate) intersects at most 3 other disjoint disks (see figure). Therefore the greedy algorithm yields a 3-approximation, i.e., it finds a disjoint set with a size of at least
1611:
1491:
1453:
1363:
1249:
662:
2243:
2195:
2083:
1979:
1829:
1794:
1759:
1325:
1163:
529:
Divide the given set of shapes into two or more subsets, such that the shapes in each subset cannot overlap the shapes in other subsets because of geometric considerations.
57:
For the general MIS problem, the best known exact algorithms are exponential. In some geometric intersection graphs, there are sub-exponential algorithms for finding a MDS.
1091:
4588:
4408:
3832:
This PTAS is more space-efficient than the PTAS based on quadtrees, and can handle a generalization where the objects may slide, but it cannot handle the weighted case.
2293:
4788:
4638:
935:
axis-parallel rectangles in the plane, all with the same height but with varying lengths. There is an algorithm that finds a disjoint set with a size of at least |MDS(
4434:
815:
782:
4077:
4085:
749:
719:
692:
4513:
4487:
2380:
for finding an MDS based on multi-level grid alignment. It has been discovered by two groups in approximately the same time, and described in two different ways.
4458:
3906:
2488:
3759:{\displaystyle E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a}}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.}
3412:
the number of labels intersected by the separator. The worst case for the algorithm is when the split in each step is in the maximum possible ratio which is
2298:
To date, it is not known whether such a guillotine separation exists. However, there are constant-factor approximation algorithms using non-guillotine cuts:
157:
Of all of the shapes xi that intersect xj (including xj itself), select the shape x that touches the fewest other shapes, i.e. x such that. N(x) is a minimum
3488:
219:
later on. However, some of these shapes themselves intersect each other, and thus in any case it is not possible that they all be in the optimal solution
4269:
60:
The general MIS problem is hard to approximate and doesn't even have a constant-factor approximation. In some geometric intersection graphs, there are
2434: + 1) apart from each other. By construction, every disk can intersect at most one horizontal line and one vertical line from its level.
3139:, such as squares or circles, of arbitrary sizes. Chan described an algorithm finds a disjoint set with a size of at least (1 −
2805:, we can simply "guess" which objects intersect the boundary in the optimal solution, and then apply divide-and-conquer to the objects inside.
83:
The MDS problem can be generalized by assigning a different weight to each shape and searching for a disjoint set with a maximum total weight.
2407:
Scale the disks so that the smallest disk has diameter 1. Partition the disks to levels, based on the logarithm of their size. I.e., the
4790:, or a deterministic algorithm with a slower run time (but still polynomial). This algorithm can be generalized to the weighted case.
969:
dimensions. If the labels have the same size in all dimensions except one, it is possible to find a similar approximation by applying
614:, it is not possible that a rectangle is intersected by more than one line. Therefore the lines partition the set of rectangles into
2295:
rectangles are separated, then it can be used in a dynamic programming approach to find a constant-factor approximation to the MDS.
5179:
Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015).
2952:
2341:
for finding an MDS using a simple shifted-grid strategy. It finds a solution within (1 − ε) of the maximum in time
1988:
1884:
1657:
4290:
525:
The most common approach to finding a MDS is divide-and-conquer. A typical algorithm in this approach looks like the following:
5497:
5258:
5200:
5156:
5111:
4891:
367:=1, and thus the greedy algorithm finds the exact MDS. To see this, assume w.l.o.g. that the intervals are vertical, and let
5386:
3117:
3093:
2377:
2338:
61:
4964:
Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). "Simple heuristics for unit disk graphs".
5308:
Erlebach, T.; Jansen, K.; Seidel, E. (2005). "Polynomial-Time
Approximation Schemes for Geometric Intersection Graphs".
3426:
429:
4192:
2899: − 1}, consider a shift of the grid in (j/k,j/k). It is possible to prove that every label will be 2
5440:
5237:
Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Pittu, Madhusudhan Reddy; Wiese, Andreas (2022-01-01),
4924:
271:
5127:
Chalermsook, Parinya; Walczak, Bartosz (2021-01-01), "Coloring and
Maximum Weight Independent Set of Rectangles",
4699:
2088:
992:
5527:
871:
823:
77:
2388:
An algorithm of
Erlebach, Jansen and Seidel finds a disjoint set with a size of at least (1 − 1/
3980:
3859:
35:
4922:
Agarwal, P. K.; Van
Kreveld, M.; Suri, S. (1998). "Label placement by maximum independent set in rectangles".
1872:, this computation is equivalent to finding an MDS from a set of intervals, and can be solved exactly in time
4693:
989:
axis-parallel rectangles in the plane. The following algorithm finds a disjoint set with a size of at least
3772:
5216:
Mitchell, Joseph S. B. (2021-06-25). "Approximating
Maximum Independent Set for Rectangles in the Plane".
4754:. This is possible either with a randomized algorithm that has a high probability of success and run time
1834:
1616:
1537:
1496:
1368:
1254:
1175:
5438:
Agarwal, P. K.; Mustafa, N. H. (2006). "Independent set of intersection graphs of convex objects in 2D".
1578:
1458:
1420:
1330:
1216:
621:
4850:
Ravi, S. S.; Hunt, H. B. (1987). "An application of the planar separator theorem to counting problems".
2203:
2155:
2053:
1949:
1799:
1764:
1729:
1295:
1133:
3289:
as low as 2/3 by a proper selection of the separator rectangle. But since we can only approximate MDS(
3167:
The algorithm is based on the following geometric separator theorem, which can be proved similarly to
499:=5, because the disk with the smallest radius intersects at most 5 other disjoint disks (see figure).
31:) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.
2305:
presented a 10-factor approximation algorithm. His algorithm is based on partitioning the plane into
69:
5480:
560:
but with varying lengths. The following algorithm finds a disjoint set with a size of at least |MDS(
5067:
5053:
Chan, T. M. (2003). "Polynomial-time approximation schemes for packing and piercing fat objects".
2349:
of roughly the same size (i.e., when the maximum-to-minimum size ratio is bounded by a constant).
1056:
154:
Choose any xj such that N(xj) is a maximum, i.e. a shape that touches as many shapes as any other.
44:
4547:
4371:
2855:). First, scale the objects such that they are all contained in the unit square. Then, consider
2269:
5475:
5062:
4284:
3168:
20:
4757:
4605:
4176:{\displaystyle T(n)=2^{O(r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{ if }}n>1}
2781:; hence the number of disjoint fat objects intersecting the boundary of that cell is at most 4
4413:
3136:
2365:
2346:
2302:
2263:
787:
754:
4871:
4047:
3335: + 1 labels are not disjoint) then just return that MDS and exit. This step takes
2461:) as the subset of disks that are not intersected by any horizontal line whose index modulo
2478:
727:
697:
670:
421:
Add an interval with the highest bottom endpoint, and delete all intervals intersecting it.
8:
5470:
Fox, J.; Pach, J. N. (2011). "Computing the
Independence Number of Intersection Graphs".
4819:
4492:
4466:
3848:
disks, such that the ratio between the largest radius and the smallest radius is at most
3112:
2683:
An algorithm of Chan finds a disjoint set with a size of at least (1 − 2/
2656:
2596:{\displaystyle |\mathrm {MDS} (D(r,s))|\geq (1-{\frac {1}{k}})^{2}\cdot |\mathrm {MDS} |}
1172:
Partition the input rectangles into three groups according to their relation to the line
970:
959:
433:
5238:
5191:
4876:
Proceedings 39th Annual
Symposium on Foundations of Computer Science (Cat. No.98CB36280)
5503:
5415:
5395:
5288:
5264:
5217:
5162:
5132:
5030:
4973:
4897:
4443:
39:
5180:
5076:
5009:"Approximation schemes for covering and packing problems in image processing and VLSI"
4937:
4664:
The algorithm is very simple; the difficult part is to prove the approximation ratio.
3591:{\displaystyle E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{ if }}m>b}
5493:
5268:
5254:
5196:
5166:
5152:
5107:
5004:
4887:
4863:
958:
The algorithm is an improvement of the above-mentioned 2-approximation, by combining
5507:
5419:
4901:
3825:. We can make the approximation factor as small as we want by a proper selection of
3123:
2245:-approximation algorithm to the more general setting, in which each rectangle has a
5485:
5449:
5405:
5377:
5348:
5317:
5246:
5186:
5142:
5099:
5072:
5034:
5020:
4983:
4941:
4933:
4879:
4859:
4823:
3835:
111:
5472:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on
Discrete Algorithms
5453:
5373:
5245:, Proceedings, Society for Industrial and Applied Mathematics, pp. 894–905,
5131:, Proceedings, Society for Industrial and Applied Mathematics, pp. 860–868,
2935:) shift, and find a maximum disjoint set of the remaining objects. Call that set
543:
514:
406:
Sort the intervals in ascending order of their bottom endpoints (this takes time
5489:
5353:
5336:
5250:
5243:
Proceedings of the 2022 Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA)
5147:
5103:
918:
Return the largest of these two unions. Its size must be at least |MDS|/2.
5410:
5381:
5321:
3392:, the error is 0 because the maximum disjoint set is calculated exactly; when
2722: ≥ 1 is a constant) if it is inside a quadtree cell of size at most
5521:
5096:
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms
5091:
4883:
4803:
4793:
3420:). Therefore the error function satisfies the following recurrence relation:
976:
4041:
The run time of this algorithm satisfies the following recurrence relation:
4987:
3103:
dimensions (with different approximation ratios) and to the weighted case.
2820:-aligned, and find a maximum disjoint set of the remaining objects in time
1097:
INITIALIZATION: sort the horizontal edges of the given rectangles by their
390:
Therefore, in the 1-dimensional case, the MDS can be found exactly in time
2252:
3092:. We can make the approximation factor as small as we want, so this is a
50:
5129:
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
5025:
5008:
4830:
Javascript code for calculating exact maximum disjoint set of rectangles
4829:
3917:. This separator theorem allows to build the following exact algorithm:
2796:-aligned, it is possible to find the exact maximum disjoint set in time
447:
5239:"A 3-Approximation Algorithm for Maximum Independent Set of Rectangles"
3376:) be the error of the above algorithm when the optimal MDS size is MDS(
2741:-aligned object that intersects the boundary of a quatree cell of size
2615:) and miss only a small fraction of the disks in the optimal solution:
5382:"Approximation Algorithms for Maximum Independent Set of Pseudo-Disks"
4946:
3169:
the proof of the existence of geometric separator for disjoint squares
2249:, and the goal is to find an independent set of maximum total weight.
922:
462:=3, because the leftmost disk (the disk whose center has the smallest
347:
53:, but finding a MDS may be easier than finding a MIS in two respects:
4978:
2345:
time and linear space. The strategy generalizes to any collection of
973:
along one of the dimensions. This also reduces the time to n^O(1/e).
664:) – each subset includes the rectangles intersected by a single line.
4820:
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
484:
352:
5293:
5222:
5137:
4023:
such subsets. For each such subset, recursively compute the MDS of
3360:
separately, and return their combination as the approximate MDS in
2703:
42:
of the shapes. Therefore, the MDS problem is a special case of the
5400:
817:. Therefore, each of the following two unions is a disjoint sets:
3124:
Fat objects with arbitrary sizes: PTAS using geometric separators
2828:) approximation, where e is the fraction of objects that are not
2675:
2373:
2334:
1575:), and calculate their union. By construction, the rectangles in
5178:
3836:
Disks with a bounded size-ratio: exact sub-exponential algorithm
556:
axis-parallel rectangles in the plane, all with the same height
2369:
2330:
5337:"Theory and application of width bounded geometric separators"
2430:, impose a grid on the plane that consists of lines that are (
544:
Axis-parallel rectangles with the same height: 2-approximation
3111:
Several divide-and-conquer algorithms are based on a certain
3051:{\displaystyle \sum _{j=0,\ldots ,k-1}{|A(j)|}\geq (k-2)|A*|}
442:
4287:
by Chan and Har-Peled finds a disjoint set of size at least
2043:{\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}
1939:{\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}
1712:{\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}
379:
must cross its bottom endpoint. Therefore, all intervals in
4670:
4361:{\displaystyle (1-O({\frac {1}{\sqrt {b}}}))\cdot |MDS(C)|}
3308:
This separator theorem allows to build the following PTAS:
1985:
It is provable by induction that, at the last step, either
1124: ≤ 2 shapes, compute the MDS directly and return.
73:
4794:
Other classes of shapes for which approximations are known
3120:
and sub-exponential exact algorithms, as explained below.
977:
Axis-parallel rectangles: Logarithmic-factor approximation
4696:, it is possible to find a disjoint set of size at least
2352:
2317:
4653:
Every exchange in the search step increases the size of
4526:
itself is independent (otherwise go to the next subset);
2816:-aligned, we can just discard the objects that are not
2253:
Axis-parallel rectangles: constant-factor approximation
721:
using the one-dimensional greedy algorithm (see above).
587:
The separation between two lines is strictly more than
4921:
3084:); the approximation factor is (1 − 2/
4760:
4702:
4608:
4550:
4495:
4469:
4446:
4416:
4374:
4293:
4195:
4088:
4050:
3983:
3862:
3775:
3610:
3491:
3429:
3181:
of fat objects, there is a rectangle that partitions
3076:*|. The return value of the algorithm is the largest
2955:
2491:
2272:
2206:
2158:
2091:
2056:
1991:
1952:
1887:
1837:
1802:
1767:
1732:
1660:
1619:
1581:
1540:
1499:
1461:
1423:
1371:
1333:
1298:
1257:
1219:
1178:
1136:
1059:
995:
874:
826:
790:
757:
730:
700:
673:
624:
274:
5307:
4809:
Curves with a bounded number of intersection points.
2789:
is a constant measuring the fatness of the objects.
2411:-th level contains all disks with diameter between (
2152:
Chalermsookk and Chuzoy have improved the factor to
250:
In particular, if we can guarantee that there is an
68:
Finding an MDS is important in applications such as
5368:
5366:
5364:
5286:
5236:
4999:
4997:
4963:
2801:
the boundary of every quadtree cell is bounded by 4
962:with the shifting technique of Hochbaum and Maass.
923:
Axis-parallel rectangles with the same height: PTAS
594:Each line intersects at least one rectangle (hence
532:
Recursively find the MDS in each subset separately.
348:
1-dimensional intervals: exact polynomial algorithm
5126:
5089:
4782:
4746:
4632:
4582:
4507:
4481:
4452:
4428:
4402:
4360:
4242:
4175:
4071:
4015:
3894:
3817:
3758:
3590:
3477:{\displaystyle E(m)=0\ \ \ \ {\text{ if }}m\leq b}
3476:
3050:
2595:
2423: ≤ 0 (the smallest disk is in level 0).
2404: > 1. It works in the following way.
2337:of identical size. Hochbaum and Maass presented a
2287:
2237:
2189:
2141:
2077:
2042:
1973:
1938:
1864:
1823:
1788:
1753:
1711:
1646:
1605:
1567:
1526:
1485:
1447:
1398:
1357:
1319:
1284:
1243:
1205:
1157:
1085:
1045:
906:
858:
809:
776:
743:
713:
686:
656:
605:Each rectangle is intersected by exactly one line.
506:is a set of arbitrary-size axis-parallel squares,
330:
5094:(2009). "Maximum Independent Set of Rectangles".
3970:Consider all possible non-overlapping subsets of
3342:Otherwise, use a geometric separator to separate
3106:
3068:) has a size of at least: (1 − 2/
266:-factor approximation, as we can guarantee that:
151:Assign N(xi) equal to the number shapes in J(xi).
5519:
5361:
4994:
520:
262:), then this greedy algorithm yields a constant
4872:"Geometric separator theorems and applications"
5437:
4243:{\displaystyle T(n)=2^{O(r\cdot {\sqrt {n}})}}
2943:). Call the real maximum disjoint set is
2469:, nor by any vertical line whose index modulu
535:Return the union of the MDSs from all subsets.
5372:
5003:
4959:
4957:
4917:
4915:
4913:
4911:
1101:-coordinate, and the vertical edges by their
331:{\displaystyle |S|\geq {\frac {|MDS(C)|}{M}}}
136:Calculate J(xi), the subset of all shapes in
5301:
4869:
4747:{\displaystyle {\frac {n}{u}}\cdot |MDS(C)|}
3346:to two subsets. Find the approximate MDS in
2142:{\displaystyle {\frac {|MDS(C)|}{\log {n}}}}
1046:{\displaystyle {\frac {|MDS(C)|}{\log {n}}}}
513:Other constants can be calculated for other
90:) denotes the maximum disjoint set in a set
4799:Line segments in the two-dimensional plane.
4657:by at least 1, and thus can happen at most
3315:. Check all possible combinations of up to
907:{\displaystyle M_{2}\cup M_{4}\cup \cdots }
859:{\displaystyle M_{1}\cup M_{3}\cup \cdots }
5048:
5046:
5044:
4954:
4908:
4253:
2200:Chalermsook and Walczak have presented an
443:Fat shapes: constant-factor approximations
34:Every set of non-overlapping shapes is an
5479:
5409:
5399:
5352:
5292:
5221:
5190:
5146:
5136:
5066:
5024:
4977:
4945:
4675:
4440:INITIALIZATION: Initialize an empty set,
4016:{\displaystyle 2^{O(r\cdot {\sqrt {n}})}}
3956:) centers are at a distance of less than
3921:Find a separator line such that at most 2
3895:{\displaystyle 2^{O(r\cdot {\sqrt {n}})}}
3281:are constants. If we could calculate MDS(
2824:. This results in a (1 −
1327:). By construction, the cardinalities of
118:INITIALIZATION: Initialize an empty set,
5215:
4849:
4671:Linear programming relaxation algorithms
2710:to the quadtree grid. An object of size
2674:
477:is a set of axis-parallel unit squares,
5469:
5465:
5463:
5433:
5431:
5429:
5341:Journal of Computer and System Sciences
5041:
4258:
5520:
4037:, and return the largest combined set.
3285:) exactly, we could make the constant
2792:Therefore, if all objects are fat and
2706:. The key concept of the algorithm is
2353:Fat objects with arbitrary sizes: PTAS
2318:Fat objects with identical sizes: PTAS
610:Since the height of all rectangles is
387:has a size of at most 1 (see figure).
344:exists for several interesting cases:
5387:Discrete & Computational Geometry
4870:Smith, W. D.; Wormald, N. C. (1998).
4463:SEARCH: Loop over all the subsets of
3818:{\displaystyle E(m)=O(m/{\sqrt {b}})}
3293:) by a constant factor, the constant
2383:
2266:of axes-parallel rectangles in which
1120:STOP CONDITION: If there are at most
965:This algorithm can be generalized to
375:. All other intervals intersected by
62:polynomial-time approximation schemes
5460:
5426:
5052:
4186:The solution to this recurrence is:
3852:. The following algorithm finds MDS(
3601:The solution to this recurrence is:
3099:Both versions can be generalized to
2907: − 2 values of
2670:
2603:, i.e., we can find the MDS only in
2339:polynomial-time approximation scheme
1865:{\displaystyle x=x_{\mathrm {med} }}
1647:{\displaystyle M_{\mathrm {right} }}
1568:{\displaystyle M_{\mathrm {right} }}
1527:{\displaystyle R_{\mathrm {right} }}
1399:{\displaystyle R_{\mathrm {right} }}
1285:{\displaystyle R_{\mathrm {right} }}
1206:{\displaystyle x=x_{\mathrm {med} }}
724:By construction, the rectangles in (
223:. The largest subset of shapes that
97:
5192:10.4230/LIPIcs.APPROX-RANDOM.2015.1
3301:remains a constant independent of |
2915:, discard the objects that are not
1606:{\displaystyle M_{\mathrm {left} }}
1486:{\displaystyle M_{\mathrm {left} }}
1448:{\displaystyle R_{\mathrm {left} }}
1358:{\displaystyle R_{\mathrm {left} }}
1244:{\displaystyle R_{\mathrm {left} }}
751:) can intersect only rectangles in
657:{\displaystyle R_{i},\ldots ,R_{m}}
428:This algorithm is analogous to the
424:Continue until no intervals remain.
106:of shapes, an approximation to MDS(
13:
5334:
5328:
2839:-aligned, we can try to make them
2765:). The boundary of a cell of size
2584:
2581:
2578:
2504:
2501:
2498:
2273:
2262:. Particularly, if there exists a
2238:{\displaystyle O(\log {\log {n}})}
2190:{\displaystyle O(\log {\log {n}})}
2078:{\displaystyle M_{\mathrm {int} }}
2069:
2066:
2063:
2034:
2031:
2028:
2025:
2022:
2007:
2004:
2001:
1998:
1974:{\displaystyle M_{\mathrm {int} }}
1965:
1962:
1959:
1930:
1927:
1924:
1921:
1918:
1903:
1900:
1897:
1894:
1856:
1853:
1850:
1824:{\displaystyle R_{\mathrm {int} }}
1815:
1812:
1809:
1789:{\displaystyle M_{\mathrm {int} }}
1780:
1777:
1774:
1754:{\displaystyle R_{\mathrm {int} }}
1745:
1742:
1739:
1703:
1700:
1697:
1694:
1691:
1676:
1673:
1670:
1667:
1638:
1635:
1632:
1629:
1626:
1597:
1594:
1591:
1588:
1559:
1556:
1553:
1550:
1547:
1518:
1515:
1512:
1509:
1506:
1477:
1474:
1471:
1468:
1439:
1436:
1433:
1430:
1390:
1387:
1384:
1381:
1378:
1349:
1346:
1343:
1340:
1320:{\displaystyle R_{\mathrm {int} }}
1311:
1308:
1305:
1276:
1273:
1270:
1267:
1264:
1235:
1232:
1229:
1226:
1197:
1194:
1191:
1158:{\displaystyle x_{\mathrm {med} }}
1149:
1146:
1143:
1105:-coordinate (this step takes time
495:is a set of arbitrary-size disks,
483:
446:
430:earliest deadline first scheduling
351:
227:all be in the optimal solution is
211:, because they are intersected by
14:
5539:
4813:
3907:width-bounded geometric separator
3400:, the error increases by at most
2679:A region quadtree with point data
2376:, of arbitrary sizes. There is a
1831:intersect a single vertical line
363:is a set of intervals on a line,
16:Concept in computational geometry
3185:into three subsets of objects –
1292:), and those intersected by it (
1251:), those entirely to its right (
110:) can be found by the following
5280:
5230:
5182:On Guillotine Cutting Sequences
3913:of the centers of all disks in
2085:have a cardinality of at least
258:is bounded by a constant (say,
239:minimizes the loss from adding
78:frequency division multiplexing
5209:
5172:
5120:
5083:
4852:Information Processing Letters
4843:
4777:
4764:
4740:
4736:
4730:
4717:
4576:
4568:
4560:
4552:
4397:
4378:
4354:
4350:
4344:
4331:
4324:
4321:
4306:
4294:
4235:
4219:
4205:
4199:
4128:
4112:
4098:
4092:
4060:
4054:
4008:
3992:
3887:
3871:
3812:
3794:
3785:
3779:
3693:
3687:
3655:
3626:
3620:
3614:
3555:
3546:
3534:
3531:
3522:
3510:
3501:
3495:
3439:
3433:
3107:Geometric separator algorithms
3044:
3033:
3029:
3017:
3009:
3005:
2999:
2992:
2859:shifts of the grid: (0,0), (1/
2589:
2573:
2560:
2540:
2533:
2529:
2526:
2514:
2508:
2493:
2282:
2276:
2232:
2210:
2184:
2162:
2119:
2115:
2109:
2096:
1981:– whichever of them is larger.
1213:: those entirely to its left (
1080:
1063:
1023:
1019:
1013:
1000:
318:
314:
308:
295:
284:
276:
1:
5077:10.1016/s0196-6774(02)00294-8
4938:10.1016/s0925-7721(98)00028-5
4694:linear programming relaxation
4688:objects and union complexity
4410:, for every integer constant
3925:/3 centers are to its right (
3297:must be larger. Fortunately,
2745:must have a size of at least
2481:, there is at least one pair
584:horizontal lines, such that:
521:Divide-and-conquer algorithms
76:circuit design, and cellular
5454:10.1016/j.comgeo.2005.12.001
4864:10.1016/0020-0190(87)90206-7
4489:whose size is between 1 and
3936:/3 centers are to its left (
3905:The algorithm is based on a
2847:the grid in multiples of (1/
2662:Return the largest of these
1086:{\displaystyle O(n\log {n})}
215:and thus cannot be added to
7:
4684:be a pseudo-disks-set with
4279:be a pseudo-disks-set with
2702:The algorithm uses shifted
1796:). Since all rectangles in
86:In the following text, MDS(
49:problem. Both problems are
10:
5544:
5490:10.1137/1.9781611973082.87
5354:10.1016/j.jcss.2010.05.003
5251:10.1137/1.9781611977073.38
5148:10.1137/1.9781611976465.54
5104:10.1137/1.9781611973068.97
4802:Arbitrary two-dimensional
4583:{\displaystyle |Y|<|X|}
4403:{\displaystyle O(n^{b+3})}
2288:{\displaystyle \Omega (n)}
383:intersect each other, and
231:. Therefore, selecting an
5411:10.1007/s00454-012-9417-5
5322:10.1137/s0097539702402676
5310:SIAM Journal on Computing
3327:)| has a size of at most
2392:) ⋅ |MDS(
2307:corner-clipped rectangles
371:be the interval with the
70:automatic label placement
64:(PTAS) for finding a MDS.
4884:10.1109/sfcs.1998.743449
4836:
4783:{\displaystyle O(n^{3})}
4633:{\displaystyle S:=S-Y+X}
2835:If most objects are not
458:is a set of unit disks,
207:, we lose the shapes in
181:and delete J(x) and N(x)
125:SEARCH: For every shape
4515:. For each such subset
4429:{\displaystyle b\geq 0}
4254:Local search algorithms
3319: + 1 labels.
3088:), and the run time is
3060:Therefore, the largest
1413:Recursively compute an
810:{\displaystyle R_{i-1}}
777:{\displaystyle R_{i+1}}
694:, compute an exact MDS
373:highest bottom endpoint
184:If there are shapes in
45:maximum independent set
5528:Computational geometry
5441:Computational Geometry
4988:10.1002/net.3230250205
4925:Computational Geometry
4784:
4748:
4634:
4584:
4509:
4483:
4454:
4430:
4404:
4362:
4285:local search algorithm
4244:
4177:
4073:
4072:{\displaystyle T(1)=1}
4017:
3896:
3819:
3760:
3592:
3478:
3416::(1 −
3052:
2903:-aligned for at least
2887: − 1)/
2879: − 1)/
2680:
2597:
2289:
2239:
2191:
2143:
2079:
2044:
1975:
1940:
1866:
1825:
1790:
1755:
1713:
1648:
1607:
1569:
1528:
1487:
1449:
1400:
1359:
1321:
1286:
1245:
1207:
1159:
1087:
1047:
951:), for every constant
908:
860:
811:
778:
745:
715:
688:
658:
488:
451:
356:
332:
21:computational geometry
5055:Journal of Algorithms
4785:
4749:
4635:
4585:
4510:
4484:
4455:
4431:
4405:
4363:
4245:
4178:
4074:
4018:
3897:
3820:
3761:
3593:
3479:
3160:, for every constant
3053:
2695:, for every constant
2678:
2598:
2419: + 1), for
2415: + 1) and (
2400:, for every constant
2303:Joseph S. B. Mitchell
2290:
2264:guillotine separation
2240:
2192:
2144:
2080:
2045:
1976:
1941:
1867:
1826:
1791:
1756:
1714:
1654:are all disjoint, so
1649:
1608:
1570:
1529:
1488:
1450:
1401:
1360:
1322:
1287:
1246:
1208:
1160:
1088:
1048:
909:
861:
812:
779:
746:
744:{\displaystyle R_{i}}
716:
714:{\displaystyle M_{i}}
689:
687:{\displaystyle R_{i}}
659:
487:
450:
355:
333:
5007:; Maass, W. (1985).
4758:
4700:
4676:Pseudo-disks: a PTAS
4645:END: return the set
4606:
4548:
4493:
4467:
4444:
4414:
4372:
4291:
4259:Pseudo-disks: a PTAS
4193:
4086:
4048:
3981:
3977:. There are at most
3860:
3773:
3608:
3489:
3427:
2953:
2489:
2479:pigeonhole principle
2270:
2204:
2156:
2089:
2054:
1989:
1950:
1885:
1835:
1800:
1765:
1730:
1658:
1617:
1579:
1538:
1497:
1459:
1421:
1369:
1331:
1296:
1255:
1217:
1176:
1134:
1057:
993:
939:)|/(1 + 1/
872:
868:Union of even MDSs:
824:
788:
755:
728:
698:
671:
622:
340:Such an upper bound
272:
191:END: return the set
188:, go back to Search.
25:maximum disjoint set
5026:10.1145/2455.214106
4508:{\displaystyle b+1}
4482:{\displaystyle C-S}
3164: > 1.
3113:geometric separator
2769:can be covered by 4
2699: > 1.
2657:dynamic programming
2623:possible values of
971:dynamic programming
960:dynamic programming
955: > 1.
820:Union of odd MDSs:
434:interval scheduling
5013:Journal of the ACM
4822:- presentation by
4780:
4744:
4630:
4580:
4529:Calculate the set
4505:
4479:
4450:
4426:
4400:
4358:
4240:
4173:
4069:
4013:
3960:/2 from the line (
3892:
3856:) exactly in time
3815:
3756:
3588:
3474:
3331:(i.e. all sets of
3311:Select a constant
3048:
2989:
2891:). I.e., for each
2681:
2593:
2384:Level partitioning
2285:
2235:
2187:
2139:
2075:
2040:
1971:
1936:
1862:
1821:
1786:
1751:
1719:is a disjoint set.
1709:
1644:
1603:
1565:
1524:
1483:
1445:
1396:
1355:
1317:
1282:
1241:
1203:
1155:
1083:
1043:
904:
856:
807:
774:
741:
711:
684:
654:
489:
452:
357:
328:
40:intersection graph
5499:978-0-89871-993-2
5260:978-1-61197-707-3
5202:978-3-939897-89-7
5185:. pp. 1–19.
5158:978-1-61197-646-5
5113:978-0-89871-680-1
5090:Chalermsook, P.;
4893:978-0-8186-9172-0
4711:
4453:{\displaystyle S}
4319:
4318:
4233:
4162:
4153:
4126:
4006:
3885:
3810:
3751:
3741:
3732:
3716:
3691:
3679:
3663:
3653:
3637:
3577:
3572:
3463:
3459:
3456:
3453:
3450:
2956:
2919:-aligned in the (
2911:. Now, for every
2737:By definition, a
2671:Shifted quadtrees
2557:
2137:
1041:
326:
98:Greedy algorithms
5535:
5512:
5511:
5483:
5474:. p. 1161.
5467:
5458:
5457:
5435:
5424:
5423:
5413:
5403:
5370:
5359:
5358:
5356:
5332:
5326:
5325:
5305:
5299:
5298:
5296:
5284:
5278:
5277:
5276:
5275:
5234:
5228:
5227:
5225:
5213:
5207:
5206:
5194:
5176:
5170:
5169:
5150:
5140:
5124:
5118:
5117:
5087:
5081:
5080:
5070:
5050:
5039:
5038:
5028:
5001:
4992:
4991:
4981:
4961:
4952:
4951:
4949:
4919:
4906:
4905:
4867:
4847:
4824:Sariel Har-Peled
4789:
4787:
4786:
4781:
4776:
4775:
4753:
4751:
4750:
4745:
4743:
4720:
4712:
4704:
4639:
4637:
4636:
4631:
4589:
4587:
4586:
4581:
4579:
4571:
4563:
4555:
4514:
4512:
4511:
4506:
4488:
4486:
4485:
4480:
4459:
4457:
4456:
4451:
4435:
4433:
4432:
4427:
4409:
4407:
4406:
4401:
4396:
4395:
4367:
4365:
4364:
4359:
4357:
4334:
4320:
4314:
4310:
4270:union complexity
4265:pseudo-disks-set
4249:
4247:
4246:
4241:
4239:
4238:
4234:
4229:
4182:
4180:
4179:
4174:
4163:
4160:
4158:
4154:
4149:
4141:
4132:
4131:
4127:
4122:
4078:
4076:
4075:
4070:
4022:
4020:
4019:
4014:
4012:
4011:
4007:
4002:
3955:
3954:
3901:
3899:
3898:
3893:
3891:
3890:
3886:
3881:
3824:
3822:
3821:
3816:
3811:
3806:
3804:
3765:
3763:
3762:
3757:
3752:
3747:
3742:
3740:
3733:
3722:
3717:
3712:
3706:
3692:
3690:
3680:
3669:
3664:
3659:
3654:
3649:
3643:
3638:
3630:
3597:
3595:
3594:
3589:
3578:
3575:
3573:
3568:
3483:
3481:
3480:
3475:
3464:
3461:
3457:
3454:
3451:
3448:
3411:
3410:
3396: >
3265:
3264:
3262:
3151:
3150:
3057:
3055:
3054:
3049:
3047:
3036:
3013:
3012:
2995:
2988:
2812:all objects are
2773:squares of size
2639: <
2602:
2600:
2599:
2594:
2592:
2587:
2576:
2568:
2567:
2558:
2550:
2536:
2507:
2496:
2294:
2292:
2291:
2286:
2244:
2242:
2241:
2236:
2231:
2230:
2196:
2194:
2193:
2188:
2183:
2182:
2148:
2146:
2145:
2140:
2138:
2136:
2135:
2123:
2122:
2099:
2093:
2084:
2082:
2081:
2076:
2074:
2073:
2072:
2049:
2047:
2046:
2041:
2039:
2038:
2037:
2012:
2011:
2010:
1980:
1978:
1977:
1972:
1970:
1969:
1968:
1945:
1943:
1942:
1937:
1935:
1934:
1933:
1908:
1907:
1906:
1871:
1869:
1868:
1863:
1861:
1860:
1859:
1830:
1828:
1827:
1822:
1820:
1819:
1818:
1795:
1793:
1792:
1787:
1785:
1784:
1783:
1760:
1758:
1757:
1752:
1750:
1749:
1748:
1718:
1716:
1715:
1710:
1708:
1707:
1706:
1681:
1680:
1679:
1653:
1651:
1650:
1645:
1643:
1642:
1641:
1612:
1610:
1609:
1604:
1602:
1601:
1600:
1574:
1572:
1571:
1566:
1564:
1563:
1562:
1533:
1531:
1530:
1525:
1523:
1522:
1521:
1492:
1490:
1489:
1484:
1482:
1481:
1480:
1454:
1452:
1451:
1446:
1444:
1443:
1442:
1405:
1403:
1402:
1397:
1395:
1394:
1393:
1364:
1362:
1361:
1356:
1354:
1353:
1352:
1326:
1324:
1323:
1318:
1316:
1315:
1314:
1291:
1289:
1288:
1283:
1281:
1280:
1279:
1250:
1248:
1247:
1242:
1240:
1239:
1238:
1212:
1210:
1209:
1204:
1202:
1201:
1200:
1164:
1162:
1161:
1156:
1154:
1153:
1152:
1127:RECURSIVE PART:
1092:
1090:
1089:
1084:
1079:
1052:
1050:
1049:
1044:
1042:
1040:
1039:
1027:
1026:
1003:
997:
913:
911:
910:
905:
897:
896:
884:
883:
865:
863:
862:
857:
849:
848:
836:
835:
816:
814:
813:
808:
806:
805:
783:
781:
780:
775:
773:
772:
750:
748:
747:
742:
740:
739:
720:
718:
717:
712:
710:
709:
693:
691:
690:
685:
683:
682:
667:For each subset
663:
661:
660:
655:
653:
652:
634:
633:
515:regular polygons
502:Similarly, when
473:Similarly, when
432:solution to the
337:
335:
334:
329:
327:
322:
321:
298:
292:
287:
279:
199:For every shape
112:greedy algorithm
5543:
5542:
5538:
5537:
5536:
5534:
5533:
5532:
5518:
5517:
5516:
5515:
5500:
5481:10.1.1.700.4445
5468:
5461:
5436:
5427:
5371:
5362:
5335:Fu, B. (2011).
5333:
5329:
5306:
5302:
5285:
5281:
5273:
5271:
5261:
5235:
5231:
5214:
5210:
5203:
5177:
5173:
5159:
5125:
5121:
5114:
5098:. p. 892.
5088:
5084:
5051:
5042:
5005:Hochbaum, D. S.
5002:
4995:
4962:
4955:
4920:
4909:
4894:
4878:. p. 232.
4848:
4844:
4839:
4816:
4796:
4771:
4767:
4759:
4756:
4755:
4739:
4716:
4703:
4701:
4698:
4697:
4678:
4673:
4607:
4604:
4603:
4575:
4567:
4559:
4551:
4549:
4546:
4545:
4537:that intersect
4494:
4491:
4490:
4468:
4465:
4464:
4445:
4442:
4441:
4415:
4412:
4411:
4385:
4381:
4373:
4370:
4369:
4353:
4330:
4309:
4292:
4289:
4288:
4261:
4256:
4228:
4215:
4211:
4194:
4191:
4190:
4159:
4142:
4140:
4136:
4121:
4108:
4104:
4087:
4084:
4083:
4049:
4046:
4045:
4036:
4030:and the MDS of
4029:
4001:
3988:
3984:
3982:
3979:
3978:
3976:
3966:
3950:
3948:
3943:), and at most
3942:
3931:
3880:
3867:
3863:
3861:
3858:
3857:
3838:
3805:
3800:
3774:
3771:
3770:
3746:
3721:
3711:
3710:
3705:
3668:
3658:
3648:
3647:
3642:
3629:
3609:
3606:
3605:
3574:
3567:
3490:
3487:
3486:
3460:
3428:
3425:
3424:
3406:
3404:
3359:
3352:
3256:
3254:
3252:
3247:
3233:
3215:
3205:
3197:
3190:
3146:
3144:
3126:
3109:
3043:
3032:
3008:
2991:
2990:
2960:
2954:
2951:
2950:
2673:
2631:(0 ≤
2588:
2577:
2572:
2563:
2559:
2549:
2532:
2497:
2492:
2490:
2487:
2486:
2426:For each level
2386:
2355:
2320:
2271:
2268:
2267:
2260:guillotine cuts
2255:
2226:
2219:
2205:
2202:
2201:
2178:
2171:
2157:
2154:
2153:
2131:
2124:
2118:
2095:
2094:
2092:
2090:
2087:
2086:
2062:
2061:
2057:
2055:
2052:
2051:
2021:
2020:
2016:
1997:
1996:
1992:
1990:
1987:
1986:
1958:
1957:
1953:
1951:
1948:
1947:
1917:
1916:
1912:
1893:
1892:
1888:
1886:
1883:
1882:
1849:
1848:
1844:
1836:
1833:
1832:
1808:
1807:
1803:
1801:
1798:
1797:
1773:
1772:
1768:
1766:
1763:
1762:
1738:
1737:
1733:
1731:
1728:
1727:
1690:
1689:
1685:
1666:
1665:
1661:
1659:
1656:
1655:
1625:
1624:
1620:
1618:
1615:
1614:
1587:
1586:
1582:
1580:
1577:
1576:
1546:
1545:
1541:
1539:
1536:
1535:
1505:
1504:
1500:
1498:
1495:
1494:
1467:
1466:
1462:
1460:
1457:
1456:
1429:
1428:
1424:
1422:
1419:
1418:
1377:
1376:
1372:
1370:
1367:
1366:
1339:
1338:
1334:
1332:
1329:
1328:
1304:
1303:
1299:
1297:
1294:
1293:
1263:
1262:
1258:
1256:
1253:
1252:
1225:
1224:
1220:
1218:
1215:
1214:
1190:
1189:
1185:
1177:
1174:
1173:
1142:
1141:
1137:
1135:
1132:
1131:
1113: log
1075:
1058:
1055:
1054:
1035:
1028:
1022:
999:
998:
996:
994:
991:
990:
979:
925:
892:
888:
879:
875:
873:
870:
869:
844:
840:
831:
827:
825:
822:
821:
795:
791:
789:
786:
785:
762:
758:
756:
753:
752:
735:
731:
729:
726:
725:
705:
701:
699:
696:
695:
678:
674:
672:
669:
668:
648:
644:
629:
625:
623:
620:
619:
572: log
546:
523:
445:
414: log
398: log
350:
317:
294:
293:
291:
283:
275:
273:
270:
269:
235:that minimizes
203:that we add to
140:that intersect
100:
36:independent set
17:
12:
11:
5:
5541:
5531:
5530:
5514:
5513:
5498:
5459:
5425:
5360:
5347:(2): 379–392.
5327:
5300:
5279:
5259:
5229:
5208:
5201:
5171:
5157:
5119:
5112:
5082:
5068:10.1.1.21.5344
5061:(2): 178–189.
5040:
4993:
4953:
4907:
4892:
4841:
4840:
4838:
4835:
4834:
4833:
4827:
4815:
4814:External links
4812:
4811:
4810:
4807:
4804:convex objects
4800:
4795:
4792:
4779:
4774:
4770:
4766:
4763:
4742:
4738:
4735:
4732:
4729:
4726:
4723:
4719:
4715:
4710:
4707:
4677:
4674:
4672:
4669:
4651:
4650:
4643:
4642:
4641:
4629:
4626:
4623:
4620:
4617:
4614:
4611:
4590:, then remove
4578:
4574:
4570:
4566:
4562:
4558:
4554:
4542:
4533:of objects in
4527:
4504:
4501:
4498:
4478:
4475:
4472:
4461:
4449:
4425:
4422:
4419:
4399:
4394:
4391:
4388:
4384:
4380:
4377:
4356:
4352:
4349:
4346:
4343:
4340:
4337:
4333:
4329:
4326:
4323:
4317:
4313:
4308:
4305:
4302:
4299:
4296:
4260:
4257:
4255:
4252:
4251:
4250:
4237:
4232:
4227:
4224:
4221:
4218:
4214:
4210:
4207:
4204:
4201:
4198:
4184:
4183:
4172:
4169:
4166:
4161: if
4157:
4152:
4148:
4145:
4139:
4135:
4130:
4125:
4120:
4117:
4114:
4111:
4107:
4103:
4100:
4097:
4094:
4091:
4080:
4079:
4068:
4065:
4062:
4059:
4056:
4053:
4039:
4038:
4034:
4027:
4010:
4005:
4000:
3997:
3994:
3991:
3987:
3974:
3968:
3964:
3940:
3929:
3889:
3884:
3879:
3876:
3873:
3870:
3866:
3837:
3834:
3814:
3809:
3803:
3799:
3796:
3793:
3790:
3787:
3784:
3781:
3778:
3767:
3766:
3755:
3750:
3745:
3739:
3736:
3731:
3728:
3725:
3720:
3715:
3709:
3704:
3701:
3698:
3695:
3689:
3686:
3683:
3678:
3675:
3672:
3667:
3662:
3657:
3652:
3646:
3641:
3636:
3633:
3628:
3625:
3622:
3619:
3616:
3613:
3599:
3598:
3587:
3584:
3581:
3576: if
3571:
3566:
3563:
3560:
3557:
3554:
3551:
3548:
3545:
3542:
3539:
3536:
3533:
3530:
3527:
3524:
3521:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3497:
3494:
3484:
3473:
3470:
3467:
3462: if
3447:
3444:
3441:
3438:
3435:
3432:
3380:) =
3366:
3365:
3357:
3350:
3340:
3271:
3270:
3269:
3268:
3267:
3266:
3245:
3239:
3231:
3225:
3213:
3203:
3195:
3188:
3177:For every set
3152:))⋅|MDS(
3125:
3122:
3108:
3105:
3046:
3042:
3039:
3035:
3031:
3028:
3025:
3022:
3019:
3016:
3011:
3007:
3004:
3001:
2998:
2994:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2959:
2672:
2669:
2668:
2667:
2660:
2591:
2586:
2583:
2580:
2575:
2571:
2566:
2562:
2556:
2553:
2548:
2545:
2542:
2539:
2535:
2531:
2528:
2525:
2522:
2519:
2516:
2513:
2510:
2506:
2503:
2500:
2495:
2445:between 0 and
2385:
2382:
2354:
2351:
2319:
2316:
2315:
2314:
2310:
2284:
2281:
2278:
2275:
2254:
2251:
2234:
2229:
2225:
2222:
2218:
2215:
2212:
2209:
2186:
2181:
2177:
2174:
2170:
2167:
2164:
2161:
2134:
2130:
2127:
2121:
2117:
2114:
2111:
2108:
2105:
2102:
2098:
2071:
2068:
2065:
2060:
2036:
2033:
2030:
2027:
2024:
2019:
2015:
2009:
2006:
2003:
2000:
1995:
1983:
1982:
1967:
1964:
1961:
1956:
1932:
1929:
1926:
1923:
1920:
1915:
1911:
1905:
1902:
1899:
1896:
1891:
1881:Return either
1879:
1878:
1877:
1858:
1855:
1852:
1847:
1843:
1840:
1817:
1814:
1811:
1806:
1782:
1779:
1776:
1771:
1747:
1744:
1741:
1736:
1720:
1705:
1702:
1699:
1696:
1693:
1688:
1684:
1678:
1675:
1672:
1669:
1664:
1640:
1637:
1634:
1631:
1628:
1623:
1599:
1596:
1593:
1590:
1585:
1561:
1558:
1555:
1552:
1549:
1544:
1520:
1517:
1514:
1511:
1508:
1503:
1479:
1476:
1473:
1470:
1465:
1441:
1438:
1435:
1432:
1427:
1411:
1392:
1389:
1386:
1383:
1380:
1375:
1351:
1348:
1345:
1342:
1337:
1313:
1310:
1307:
1302:
1278:
1275:
1272:
1269:
1266:
1261:
1237:
1234:
1231:
1228:
1223:
1199:
1196:
1193:
1188:
1184:
1181:
1170:
1165:be the median
1151:
1148:
1145:
1140:
1125:
1118:
1082:
1078:
1074:
1071:
1068:
1065:
1062:
1038:
1034:
1031:
1025:
1021:
1018:
1015:
1012:
1009:
1006:
1002:
978:
975:
924:
921:
920:
919:
916:
915:
914:
903:
900:
895:
891:
887:
882:
878:
866:
855:
852:
847:
843:
839:
834:
830:
804:
801:
798:
794:
771:
768:
765:
761:
738:
734:
722:
708:
704:
681:
677:
665:
651:
647:
643:
640:
637:
632:
628:
608:
607:
606:
603:
592:
545:
542:
537:
536:
533:
530:
522:
519:
444:
441:
426:
425:
422:
419:
349:
346:
325:
320:
316:
313:
310:
307:
304:
301:
297:
290:
286:
282:
278:
197:
196:
189:
182:
171:
160:
159:
158:
155:
152:
149:
123:
99:
96:
66:
65:
58:
15:
9:
6:
4:
3:
2:
5540:
5529:
5526:
5525:
5523:
5509:
5505:
5501:
5495:
5491:
5487:
5482:
5477:
5473:
5466:
5464:
5455:
5451:
5447:
5443:
5442:
5434:
5432:
5430:
5421:
5417:
5412:
5407:
5402:
5397:
5393:
5389:
5388:
5383:
5379:
5378:Har-Peled, S.
5375:
5369:
5367:
5365:
5355:
5350:
5346:
5342:
5338:
5331:
5323:
5319:
5315:
5311:
5304:
5295:
5290:
5283:
5270:
5266:
5262:
5256:
5252:
5248:
5244:
5240:
5233:
5224:
5219:
5212:
5204:
5198:
5193:
5188:
5184:
5183:
5175:
5168:
5164:
5160:
5154:
5149:
5144:
5139:
5134:
5130:
5123:
5115:
5109:
5105:
5101:
5097:
5093:
5086:
5078:
5074:
5069:
5064:
5060:
5056:
5049:
5047:
5045:
5036:
5032:
5027:
5022:
5018:
5014:
5010:
5006:
5000:
4998:
4989:
4985:
4980:
4975:
4971:
4967:
4960:
4958:
4948:
4943:
4939:
4935:
4931:
4927:
4926:
4918:
4916:
4914:
4912:
4903:
4899:
4895:
4889:
4885:
4881:
4877:
4873:
4865:
4861:
4857:
4853:
4846:
4842:
4831:
4828:
4825:
4821:
4818:
4817:
4808:
4805:
4801:
4798:
4797:
4791:
4772:
4768:
4761:
4733:
4727:
4724:
4721:
4713:
4708:
4705:
4695:
4691:
4687:
4683:
4668:
4665:
4662:
4660:
4656:
4648:
4644:
4627:
4624:
4621:
4618:
4615:
4612:
4609:
4601:
4597:
4593:
4572:
4564:
4556:
4543:
4540:
4536:
4532:
4528:
4525:
4521:
4520:
4518:
4502:
4499:
4496:
4476:
4473:
4470:
4462:
4447:
4439:
4438:
4437:
4423:
4420:
4417:
4392:
4389:
4386:
4382:
4375:
4347:
4341:
4338:
4335:
4327:
4315:
4311:
4303:
4300:
4297:
4286:
4283:objects. A
4282:
4278:
4273:
4271:
4266:
4230:
4225:
4222:
4216:
4212:
4208:
4202:
4196:
4189:
4188:
4187:
4170:
4167:
4164:
4155:
4150:
4146:
4143:
4137:
4133:
4123:
4118:
4115:
4109:
4105:
4101:
4095:
4089:
4082:
4081:
4066:
4063:
4057:
4051:
4044:
4043:
4042:
4033:
4026:
4003:
3998:
3995:
3989:
3985:
3973:
3969:
3963:
3959:
3953:
3946:
3939:
3935:
3928:
3924:
3920:
3919:
3918:
3916:
3912:
3908:
3903:
3882:
3877:
3874:
3868:
3864:
3855:
3851:
3847:
3843:
3833:
3830:
3828:
3807:
3801:
3797:
3791:
3788:
3782:
3776:
3753:
3748:
3743:
3737:
3734:
3729:
3726:
3723:
3718:
3713:
3707:
3702:
3699:
3696:
3684:
3681:
3676:
3673:
3670:
3665:
3660:
3650:
3644:
3639:
3634:
3631:
3623:
3617:
3611:
3604:
3603:
3602:
3585:
3582:
3579:
3569:
3564:
3561:
3558:
3552:
3549:
3543:
3540:
3537:
3528:
3525:
3519:
3516:
3513:
3507:
3504:
3498:
3492:
3485:
3471:
3468:
3465:
3445:
3442:
3436:
3430:
3423:
3422:
3421:
3419:
3415:
3409:
3403:
3399:
3395:
3391:
3388: ≤
3387:
3383:
3379:
3375:
3371:
3363:
3356:
3349:
3345:
3341:
3338:
3334:
3330:
3326:
3322:
3321:
3320:
3318:
3314:
3309:
3306:
3304:
3300:
3296:
3292:
3288:
3284:
3280:
3276:
3260:
3251:
3244:
3240:
3237:
3230:
3226:
3223:
3219:
3212:
3208:
3207:
3206:, such that:
3202:
3198:
3191:
3184:
3180:
3176:
3175:
3174:
3173:
3172:
3170:
3165:
3163:
3159:
3155:
3149:
3142:
3138:
3135:
3131:
3121:
3119:
3114:
3104:
3102:
3097:
3095:
3091:
3087:
3083:
3079:
3075:
3071:
3067:
3063:
3058:
3040:
3037:
3026:
3023:
3020:
3014:
3002:
2996:
2985:
2982:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2957:
2948:
2946:
2942:
2938:
2934:
2930:
2926:
2922:
2918:
2914:
2910:
2906:
2902:
2898:
2894:
2890:
2886:
2882:
2878:
2874:
2870:
2866:
2862:
2858:
2854:
2850:
2846:
2842:
2838:
2833:
2831:
2827:
2823:
2819:
2815:
2811:
2806:
2804:
2799:
2795:
2790:
2788:
2784:
2780:
2776:
2772:
2768:
2764:
2760:
2756:
2752:
2748:
2744:
2740:
2735:
2733:
2730: ≤
2729:
2725:
2721:
2717:
2713:
2709:
2705:
2700:
2698:
2694:
2690:
2687:)⋅|MDS(
2686:
2677:
2665:
2661:
2658:
2654:
2650:
2646:
2643:), calculate
2642:
2638:
2634:
2630:
2626:
2622:
2618:
2617:
2616:
2614:
2610:
2606:
2569:
2564:
2554:
2551:
2546:
2543:
2537:
2523:
2520:
2517:
2511:
2484:
2480:
2476:
2472:
2468:
2464:
2460:
2456:
2452:
2448:
2444:
2440:
2435:
2433:
2429:
2424:
2422:
2418:
2414:
2410:
2405:
2403:
2399:
2395:
2391:
2381:
2379:
2375:
2371:
2367:
2364:
2360:
2350:
2348:
2344:
2340:
2336:
2332:
2329:
2325:
2313:(2+ε)-factor.
2311:
2308:
2304:
2301:
2300:
2299:
2296:
2279:
2265:
2261:
2250:
2248:
2227:
2223:
2220:
2216:
2213:
2207:
2198:
2179:
2175:
2172:
2168:
2165:
2159:
2150:
2132:
2128:
2125:
2112:
2106:
2103:
2100:
2058:
2017:
2013:
1993:
1954:
1913:
1909:
1889:
1880:
1875:
1845:
1841:
1838:
1804:
1769:
1734:
1725:
1721:
1686:
1682:
1662:
1621:
1583:
1542:
1501:
1463:
1425:
1416:
1412:
1409:
1373:
1335:
1300:
1259:
1221:
1186:
1182:
1179:
1171:
1168:
1138:
1129:
1128:
1126:
1123:
1119:
1116:
1112:
1108:
1104:
1100:
1096:
1095:
1094:
1076:
1072:
1069:
1066:
1060:
1036:
1032:
1029:
1016:
1010:
1007:
1004:
988:
984:
974:
972:
968:
963:
961:
956:
954:
950:
946:
942:
938:
934:
930:
917:
901:
898:
893:
889:
885:
880:
876:
867:
853:
850:
845:
841:
837:
832:
828:
819:
818:
802:
799:
796:
792:
769:
766:
763:
759:
736:
732:
723:
706:
702:
679:
675:
666:
649:
645:
641:
638:
635:
630:
626:
617:
613:
609:
604:
601:
598: ≤
597:
593:
590:
586:
585:
583:
579:
578:
577:
575:
571:
567:
564:)|/2 in time
563:
559:
555:
551:
541:
534:
531:
528:
527:
526:
518:
516:
511:
509:
505:
500:
498:
494:
486:
482:
480:
476:
471:
469:
465:
461:
457:
449:
440:
437:
435:
431:
423:
420:
417:
413:
409:
405:
404:
403:
401:
397:
393:
388:
386:
382:
378:
374:
370:
366:
362:
354:
345:
343:
338:
323:
311:
305:
302:
299:
288:
280:
267:
265:
261:
257:
253:
248:
246:
242:
238:
234:
230:
226:
222:
218:
214:
210:
206:
202:
194:
190:
187:
183:
180:
176:
172:
169:
165:
161:
156:
153:
150:
147:
143:
139:
135:
134:
132:
128:
124:
121:
117:
116:
115:
113:
109:
105:
95:
93:
89:
84:
81:
79:
75:
71:
63:
59:
56:
55:
54:
52:
48:
46:
41:
37:
32:
30:
26:
22:
5471:
5445:
5439:
5391:
5385:
5344:
5340:
5330:
5313:
5309:
5303:
5282:
5272:, retrieved
5242:
5232:
5211:
5181:
5174:
5128:
5122:
5095:
5085:
5058:
5054:
5016:
5012:
4979:math/9409226
4969:
4965:
4932:(3–4): 209.
4929:
4923:
4875:
4855:
4851:
4845:
4689:
4685:
4681:
4679:
4666:
4663:
4658:
4654:
4652:
4646:
4599:
4595:
4591:
4538:
4534:
4530:
4523:
4522:Verify that
4516:
4280:
4276:
4274:
4264:
4262:
4185:
4040:
4031:
4024:
3971:
3961:
3957:
3951:
3944:
3937:
3933:
3932:), at most 2
3926:
3922:
3914:
3910:
3904:
3853:
3849:
3845:
3844:be a set of
3841:
3839:
3831:
3826:
3768:
3600:
3417:
3413:
3407:
3401:
3397:
3393:
3389:
3385:
3381:
3377:
3373:
3369:
3367:
3361:
3354:
3347:
3343:
3336:
3332:
3328:
3324:
3316:
3312:
3310:
3307:
3302:
3298:
3294:
3290:
3286:
3282:
3278:
3274:
3272:
3258:
3249:
3242:
3235:
3228:
3221:
3217:
3210:
3200:
3193:
3186:
3182:
3178:
3166:
3161:
3157:
3153:
3147:
3140:
3133:
3132:be a set of
3129:
3127:
3110:
3100:
3098:
3089:
3085:
3081:
3077:
3073:
3069:
3065:
3061:
3059:
2949:
2944:
2940:
2936:
2932:
2928:
2924:
2920:
2916:
2912:
2908:
2904:
2900:
2896:
2892:
2888:
2884:
2880:
2876:
2872:
2868:
2864:
2860:
2856:
2852:
2848:
2844:
2843:-aligned by
2840:
2836:
2834:
2829:
2825:
2821:
2817:
2813:
2809:
2807:
2802:
2797:
2793:
2791:
2786:
2782:
2778:
2774:
2770:
2766:
2762:
2758:
2754:
2750:
2746:
2742:
2738:
2736:
2731:
2727:
2723:
2719:
2715:
2711:
2707:
2701:
2696:
2692:
2688:
2684:
2682:
2663:
2652:
2648:
2644:
2640:
2636:
2632:
2628:
2624:
2620:
2612:
2608:
2604:
2482:
2474:
2470:
2466:
2462:
2458:
2454:
2450:
2446:
2442:
2438:
2436:
2431:
2427:
2425:
2420:
2416:
2412:
2408:
2406:
2401:
2397:
2393:
2389:
2387:
2362:
2361:be a set of
2358:
2356:
2342:
2327:
2326:be a set of
2323:
2321:
2306:
2297:
2259:
2256:
2246:
2199:
2151:
1984:
1876:(see above).
1873:
1723:
1414:
1407:
1406:are at most
1169:-coordinate.
1166:
1121:
1114:
1110:
1106:
1102:
1098:
986:
985:be a set of
982:
980:
966:
964:
957:
952:
948:
944:
940:
936:
932:
931:be a set of
928:
926:
615:
611:
599:
595:
588:
581:
573:
569:
565:
561:
557:
553:
552:be a set of
549:
547:
538:
524:
512:
507:
503:
501:
496:
492:
490:
478:
474:
472:
467:
463:
459:
455:
453:
438:
427:
415:
411:
407:
399:
395:
391:
389:
384:
380:
376:
372:
368:
364:
360:
358:
341:
339:
268:
263:
259:
255:
251:
249:
244:
240:
236:
232:
228:
224:
220:
216:
212:
208:
204:
200:
198:
192:
185:
178:
174:
167:
163:
145:
141:
137:
130:
126:
119:
107:
103:
102:Given a set
101:
91:
87:
85:
82:
67:
43:
33:
28:
24:
18:
5374:Chan, T. M.
5316:(6): 1302.
5092:Chuzhoy, J.
5019:: 130–136.
4598:and insert
3909:on the set
3234:)| ≤ a|MDS(
3156:)| in time
3137:fat objects
2691:)| in time
2396:)| in time
2366:fat objects
2347:fat objects
1722:Compute an
1415:approximate
256:|MDS(N(x))|
237:|MDS(N(x))|
144:(including
51:NP complete
5394:(2): 373.
5294:2106.00623
5274:2022-09-29
5223:2101.00326
5138:2007.07880
4947:1874/18908
4858:(5): 317.
4667:See also.
2895:in {0,...,
2875:), ..., ((
2832:-aligned.
2714:is called
2485:such that
2437:For every
2368:, such as
1874:O(n log n)
943:) in time
254:for which
5476:CiteSeerX
5448:(2): 83.
5401:1103.1431
5269:235265867
5167:220525811
5063:CiteSeerX
4972:(2): 59.
4714:⋅
4619:−
4474:−
4421:≥
4328:⋅
4301:−
4226:⋅
4119:⋅
3999:⋅
3878:⋅
3744:⋅
3735:−
3727:−
3703:−
3697:⋅
3682:−
3674:−
3565:⋅
3550:⋅
3541:−
3517:⋅
3469:≤
3041:∗
3024:−
3015:≥
2983:−
2974:…
2958:∑
2947:*. Then:
2716:k-aligned
2708:alignment
2704:quadtrees
2570:⋅
2547:−
2538:≥
2477:. By the
2449:, define
2274:Ω
2224:
2217:
2176:
2169:
2129:
2014:∪
1910:∪
1683:∪
1493:) and in
1073:
1053:in time
1033:
902:⋯
899:∪
886:∪
854:⋯
851:∪
838:∪
800:−
639:…
618:subsets (
436:problem.
385:MDS(N(x))
289:≥
229:MDS(N(x))
5522:Category
5508:15850862
5420:38183751
5380:(2012).
4966:Networks
4902:17962961
4692:. Using
4368:in time
3323:If |MDS(
3246:boundary
3204:boundary
2845:shifting
2785:, where
2655:) using
2619:For all
148:itself).
5035:2383627
4661:times.
3949:√
3405:√
3384:. When
3358:outside
3253:√
3232:outside
3196:outside
3145:√
2718:(where
2374:circles
2370:squares
2335:circles
2331:squares
1726:MDS in
1417:MDS in
173:Remove
38:in the
5506:
5496:
5478:
5418:
5267:
5257:
5199:
5165:
5155:
5110:
5065:
5033:
4900:
4890:
3769:i.e.,
3458:
3455:
3452:
3449:
3351:inside
3273:where
3263:|
3255:|
3214:inside
3189:inside
2867:), (2/
2810:almost
2247:weight
784:or in
468:MDS(C)
221:MDS(S)
5504:S2CID
5416:S2CID
5396:arXiv
5289:arXiv
5265:S2CID
5218:arXiv
5163:S2CID
5133:arXiv
5031:S2CID
4974:arXiv
4898:S2CID
4837:Notes
4594:from
4035:right
3930:right
3339:time.
3241:|MDS(
3227:|MDS(
3220:|MDS(
3216:)| ≤
3209:|MDS(
3118:PTASs
2757:>
2666:sets.
2483:(r,s)
1724:exact
580:Draw
491:When
454:When
359:When
177:from
47:(MIS)
5494:ISBN
5255:ISBN
5197:ISBN
5153:ISBN
5108:ISBN
4888:ISBN
4680:Let
4565:<
4275:Let
4168:>
4028:left
3941:left
3840:Let
3583:>
3368:Let
3353:and
3277:and
3257:MDS(
3248:)|
3199:and
3128:Let
3094:PTAS
2378:PTAS
2357:Let
2322:Let
1613:and
1365:and
1130:Let
981:Let
927:Let
548:Let
510:=4.
481:=2.
470:/3.
402:):
381:N(x)
209:N(x)
162:Add
74:VLSI
23:, a
5486:doi
5450:doi
5406:doi
5349:doi
5318:doi
5247:doi
5187:doi
5143:doi
5100:doi
5073:doi
5021:doi
4984:doi
4942:hdl
4934:doi
4880:doi
4860:doi
4544:If
3975:int
3965:int
3305:|.
2871:,2/
2863:,1/
2851:,1/
2808:If
2734:).
2473:is
2465:is
2372:or
2333:or
2221:log
2214:log
2173:log
2166:log
2126:log
2050:or
1946:or
1410:/2.
1117:)).
1070:log
1030:log
576:):
418:)).
243:to
225:can
166:to
129:in
29:MDS
19:In
5524::
5502:.
5492:.
5484:.
5462:^
5446:34
5444:.
5428:^
5414:.
5404:.
5392:48
5390:.
5384:.
5376:;
5363:^
5345:77
5343:.
5339:.
5314:34
5312:.
5263:,
5253:,
5241:,
5195:.
5161:,
5151:,
5141:,
5106:.
5071:.
5059:46
5057:.
5043:^
5029:.
5017:32
5015:.
5011:.
4996:^
4982:.
4970:25
4968:.
4956:^
4940:.
4930:11
4928:.
4910:^
4896:.
4886:.
4874:.
4868:,
4856:25
4854:.
4613::=
4602::
4519::
4436::
4263:A
3967:).
3902:.
3829:.
3238:)|
3224:)|
3192:,
3171::
3096:.
3072:)|
2883:,(
2803:kc
2783:kc
2732:kr
2724:kr
2441:,
2197:.
2149:.
1093::
602:).
517:.
247:.
179:C,
146:xi
142:xi
133::
127:xi
114::
94:.
80:.
72:,
5510:.
5488::
5456:.
5452::
5422:.
5408::
5398::
5357:.
5351::
5324:.
5320::
5297:.
5291::
5249::
5226:.
5220::
5205:.
5189::
5145::
5135::
5116:.
5102::
5079:.
5075::
5037:.
5023::
4990:.
4986::
4976::
4950:.
4944::
4936::
4904:.
4882::
4866:.
4862::
4832:.
4826:.
4806:.
4778:)
4773:3
4769:n
4765:(
4762:O
4741:|
4737:)
4734:C
4731:(
4728:S
4725:D
4722:M
4718:|
4709:u
4706:n
4690:u
4686:n
4682:C
4659:n
4655:S
4649:.
4647:S
4640:.
4628:X
4625:+
4622:Y
4616:S
4610:S
4600:X
4596:S
4592:Y
4577:|
4573:X
4569:|
4561:|
4557:Y
4553:|
4541:.
4539:X
4535:S
4531:Y
4524:X
4517:X
4503:1
4500:+
4497:b
4477:S
4471:C
4460:.
4448:S
4424:0
4418:b
4398:)
4393:3
4390:+
4387:b
4383:n
4379:(
4376:O
4355:|
4351:)
4348:C
4345:(
4342:S
4339:D
4336:M
4332:|
4325:)
4322:)
4316:b
4312:1
4307:(
4304:O
4298:1
4295:(
4281:n
4277:C
4236:)
4231:n
4223:r
4220:(
4217:O
4213:2
4209:=
4206:)
4203:n
4200:(
4197:T
4171:1
4165:n
4156:)
4151:3
4147:n
4144:2
4138:(
4134:T
4129:)
4124:n
4116:r
4113:(
4110:O
4106:2
4102:=
4099:)
4096:n
4093:(
4090:T
4067:1
4064:=
4061:)
4058:1
4055:(
4052:T
4032:C
4025:C
4009:)
4004:n
3996:r
3993:(
3990:O
3986:2
3972:C
3962:C
3958:r
3952:n
3947:(
3945:O
3938:C
3934:n
3927:C
3923:n
3915:C
3911:Q
3888:)
3883:n
3875:r
3872:(
3869:O
3865:2
3854:C
3850:r
3846:n
3842:C
3827:b
3813:)
3808:b
3802:/
3798:m
3795:(
3792:O
3789:=
3786:)
3783:m
3780:(
3777:E
3754:.
3749:m
3738:1
3730:a
3724:1
3719:+
3714:a
3708:c
3700:m
3694:)
3688:)
3685:1
3677:a
3671:1
3666:+
3661:a
3656:(
3651:b
3645:c
3640:+
3635:b
3632:0
3627:(
3624:=
3621:)
3618:m
3615:(
3612:E
3586:b
3580:m
3570:m
3562:c
3559:+
3556:)
3553:m
3547:)
3544:a
3538:1
3535:(
3532:(
3529:E
3526:+
3523:)
3520:m
3514:a
3511:(
3508:E
3505:=
3502:)
3499:m
3496:(
3493:E
3472:b
3466:m
3446:0
3443:=
3440:)
3437:m
3434:(
3431:E
3418:a
3414:a
3408:m
3402:c
3398:b
3394:m
3390:b
3386:m
3382:m
3378:C
3374:m
3372:(
3370:E
3364:.
3362:C
3355:C
3348:C
3344:C
3337:n
3333:b
3329:b
3325:C
3317:b
3313:b
3303:C
3299:a
3295:a
3291:C
3287:a
3283:C
3279:c
3275:a
3261:)
3259:C
3250:c
3243:C
3236:C
3229:C
3222:C
3218:a
3211:C
3201:C
3194:C
3187:C
3183:C
3179:C
3162:b
3158:n
3154:C
3148:b
3143:(
3141:O
3134:n
3130:C
3101:d
3090:n
3086:k
3082:j
3080:(
3078:A
3074:A
3070:k
3066:j
3064:(
3062:A
3045:|
3038:A
3034:|
3030:)
3027:2
3021:k
3018:(
3010:|
3006:)
3003:j
3000:(
2997:A
2993:|
2986:1
2980:k
2977:,
2971:,
2968:0
2965:=
2962:j
2945:A
2941:j
2939:(
2937:A
2933:k
2931:/
2929:j
2927:,
2925:k
2923:/
2921:j
2917:k
2913:j
2909:j
2905:k
2901:k
2897:k
2893:j
2889:k
2885:k
2881:k
2877:k
2873:k
2869:k
2865:k
2861:k
2857:k
2853:k
2849:k
2841:k
2837:k
2830:k
2826:e
2822:n
2818:k
2814:k
2798:n
2794:k
2787:c
2779:k
2777:/
2775:R
2771:k
2767:R
2763:k
2761:/
2759:R
2755:r
2753:(
2751:k
2749:/
2747:R
2743:R
2739:k
2728:R
2726:(
2720:k
2712:r
2697:k
2693:n
2689:C
2685:k
2664:k
2659:.
2653:s
2651:,
2649:r
2647:(
2645:D
2641:k
2637:s
2635:,
2633:r
2629:s
2627:,
2625:r
2621:k
2613:s
2611:,
2609:r
2607:(
2605:D
2590:|
2585:S
2582:D
2579:M
2574:|
2565:2
2561:)
2555:k
2552:1
2544:1
2541:(
2534:|
2530:)
2527:)
2524:s
2521:,
2518:r
2515:(
2512:D
2509:(
2505:S
2502:D
2499:M
2494:|
2475:s
2471:k
2467:r
2463:k
2459:s
2457:,
2455:r
2453:(
2451:D
2447:k
2443:s
2439:r
2432:k
2428:j
2421:j
2417:k
2413:k
2409:j
2402:k
2398:n
2394:C
2390:k
2363:n
2359:C
2343:n
2328:n
2324:C
2309:.
2283:)
2280:n
2277:(
2233:)
2228:n
2211:(
2208:O
2185:)
2180:n
2163:(
2160:O
2133:n
2120:|
2116:)
2113:C
2110:(
2107:S
2104:D
2101:M
2097:|
2070:t
2067:n
2064:i
2059:M
2035:t
2032:h
2029:g
2026:i
2023:r
2018:M
2008:t
2005:f
2002:e
1999:l
1994:M
1966:t
1963:n
1960:i
1955:M
1931:t
1928:h
1925:g
1922:i
1919:r
1914:M
1904:t
1901:f
1898:e
1895:l
1890:M
1857:d
1854:e
1851:m
1846:x
1842:=
1839:x
1816:t
1813:n
1810:i
1805:R
1781:t
1778:n
1775:i
1770:M
1761:(
1746:t
1743:n
1740:i
1735:R
1704:t
1701:h
1698:g
1695:i
1692:r
1687:M
1677:t
1674:f
1671:e
1668:l
1663:M
1639:t
1636:h
1633:g
1630:i
1627:r
1622:M
1598:t
1595:f
1592:e
1589:l
1584:M
1560:t
1557:h
1554:g
1551:i
1548:r
1543:M
1534:(
1519:t
1516:h
1513:g
1510:i
1507:r
1502:R
1478:t
1475:f
1472:e
1469:l
1464:M
1455:(
1440:t
1437:f
1434:e
1431:l
1426:R
1408:n
1391:t
1388:h
1385:g
1382:i
1379:r
1374:R
1350:t
1347:f
1344:e
1341:l
1336:R
1312:t
1309:n
1306:i
1301:R
1277:t
1274:h
1271:g
1268:i
1265:r
1260:R
1236:t
1233:f
1230:e
1227:l
1222:R
1198:d
1195:e
1192:m
1187:x
1183:=
1180:x
1167:x
1150:d
1147:e
1144:m
1139:x
1122:n
1115:n
1111:n
1109:(
1107:O
1103:x
1099:y
1081:)
1077:n
1067:n
1064:(
1061:O
1037:n
1024:|
1020:)
1017:C
1014:(
1011:S
1008:D
1005:M
1001:|
987:n
983:C
967:d
953:k
949:n
947:(
945:O
941:k
937:C
933:n
929:C
894:4
890:M
881:2
877:M
846:3
842:M
833:1
829:M
803:1
797:i
793:R
770:1
767:+
764:i
760:R
737:i
733:R
707:i
703:M
680:i
676:R
650:m
646:R
642:,
636:,
631:i
627:R
616:m
612:H
600:n
596:m
591:.
589:H
582:m
574:n
570:n
568:(
566:O
562:C
558:H
554:n
550:C
508:M
504:C
497:M
493:C
479:M
475:C
464:x
460:M
456:C
416:n
412:n
410:(
408:O
400:n
396:n
394:(
392:O
377:x
369:x
365:M
361:C
342:M
324:M
319:|
315:)
312:C
309:(
306:S
303:D
300:M
296:|
285:|
281:S
277:|
264:M
260:M
252:x
245:S
241:x
233:x
217:S
213:x
205:S
201:x
195:.
193:S
186:C
175:x
170:.
168:S
164:x
138:C
131:C
122:.
120:S
108:C
104:C
92:C
88:C
27:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
