20:
2983:
6005:
2707:
2738:
8586:
With the above idea, the dominant cost of algorithm lies in the pre-processing, i.e., the computation of the convex hulls of the groups. To reduce this cost, we may consider reusing hulls computed from the previous iteration and merging them as the group size is
5817:
8011:
2517:
7631:
2978:{\displaystyle \sum _{t=0}^{\lceil \log \log h\rceil }O\left(n\log \left(2^{2^{t}}\right)\right)=O(n)\sum _{t=0}^{\lceil \log \log h\rceil }2^{t}=O\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)=O(n\log h).}
6119:
5004:
4889:
3031:
algorithm to compute the 3-dimensional convex hull by
Preparata and Hong should be used instead of Graham scan, and a 3-dimensional version of Jarvis's march needs to be used. The time complexity remains
4319:
4604:
7739:
4719:
7092:
1695:
2468:
6763:
6581:
6362:
8331:
7788:
7040:
6986:
3078:
In the following pseudocode, text between parentheses and in italic are comments. To fully understand the following pseudocode, it is recommended that the reader is already familiar with
877:
4373:
7412:
7131:
5278:
6000:{\displaystyle {\mathcal {O}}(mK\log m)={\mathcal {O}}(m\left\lceil {\frac {n}{m}}\right\rceil \log m)={\mathcal {O}}(n\log m)={\mathcal {O}}(n\log 2^{2^{t}})={\mathcal {O}}(n2^{t}).}
5411:
5352:
4811:
2337:
5137:
4201:
3855:
7314:
7275:
6904:
5803:
3415:
951:
578:
3615:
511:
5485:
1230:
1106:
5648:
3808:
3323:
8509:
8393:
8140:
4151:
2509:
1521:
1433:
6821:
6157:
5042:
4530:
4416:
1169:
6042:
4927:
3892:
1874:
8796:
8753:
8715:
6937:
3068:
3029:
2215:
2154:
2033:
1912:
1621:
1579:
736:
259:
181:
123:
1468:
641:
8463:
8227:
8061:
7816:
7184:
6452:
4265:
4060:
3744:
1263:
428:
8535:
5739:
2092:
8254:
8088:
7439:
6499:
6414:
6222:
5196:
5169:
5095:
4481:
4004:
3535:
3483:
3451:
1364:
1337:
1290:
1005:
978:
698:
671:
221:
8630:
1773:
1744:
809:
8189:
7345:
362:
8816:
8670:
8650:
8560:
8430:
8163:
7808:
7484:
7459:
7151:
6783:
6686:
6661:
6641:
6621:
6601:
6472:
6387:
6285:
6265:
6195:
5759:
5713:
5693:
5668:
5604:
5579:
5554:
5525:
5505:
5444:
5068:
4752:
4624:
4563:
4449:
4227:
4105:
4080:
4029:
3977:
3957:
3937:
3912:
3764:
3713:
3693:
3664:
3644:
3559:
3503:
3343:
3285:
3265:
3237:
3217:
3197:
3171:
3151:
3124:
3104:
2730:
2409:
2389:
2369:
2275:
2255:
2235:
2177:
2112:
2066:
1995:
1972:
1952:
1932:
1833:
1813:
1793:
1715:
1541:
1384:
1310:
1126:
1045:
1025:
780:
760:
598:
471:
448:
402:
382:
336:
316:
296:
143:
85:
65:
2702:{\displaystyle m=2^{2^{t}}\geq h\iff \log \left(2^{2^{t}}\right)\geq \log h\iff 2^{t}\geq \log h\iff \log {2^{t}}\geq \log {\log h}\iff t\geq \log {\log h},}
8760:
Constructing output sensitive algorithms for higher dimensional convex hulls. With the use of grouping points and using efficient data structures,
8580:
When computing the convex hulls of the subsets, eliminate the points that are not in the convex hull from consideration in subsequent executions.
7492:
8583:
The convex hulls of larger point sets can be obtained by merging previously calculated convex hulls, instead of recomputing from scratch.
6047:
4932:
8596:
Chan's paper contains some other problems whose known algorithms can be made optimal output sensitive using his technique, for example:
265:, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.
4821:
2237:
increases too slowly between passes, the number of iterations may be large; on the other hand, if it rises too quickly, the first
4270:
4568:
8905:
7655:
1746:
which is negligible compared to the computation for all subsets. Jarvis's march completes when the process has been repeated
8942:
8857:
4632:
384:, the number of vertices in the output convex hull, is not known at the start. Multiple passes with increasing values of
7045:
1626:
2414:
8576:
Chan's paper contains several suggestions that may improve the practical performance of the algorithm, for example:
6691:
6509:
6290:
23:
A 2D demo for Chan's algorithm. Note however that the algorithm divides the points arbitrarily, not by x-coordinate.
8951:
8265:
262:
7744:
6996:
6942:
814:
9015:
4329:
7350:
7097:
5204:
8982:
5357:
5298:
4757:
2280:
5100:
4162:
3818:
7280:
7203:
6832:
5769:
3351:
889:
516:
5766:(In this modified version of Jarvis march, we perform an operation inside the innermost loop which takes
3572:
476:
145:
is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an
5454:
1174:
1050:
5614:
5533:
3774:
3295:
40:
8468:
8344:
8099:
4326:
If the "doubling scheme" is used, though, the resulting time complexity of this Chan's algorithm is
4110:
2473:
1477:
1389:
6794:
6130:
5015:
4487:
4381:
1131:
6014:
4899:
3865:
3083:
2115:
1838:
883:
8763:
8720:
8682:
8006:{\displaystyle p_{i+1}:=JARVIS\_NEXT\_CH\_POINT(p_{i-1},p_{i},(q_{i,1},q_{i,2},\dots ,q_{i,K}))}
6909:
3035:
2996:
2182:
2121:
2000:
1879:
1584:
1546:
703:
226:
148:
90:
8886:
Nielsen, Frank (2000). "Grouping and
Querying: A Paradigm to Get Output-Sensitive Algorithms".
8828:
1438:
28:
8980:
Hershberger, John (1989). "Finding the upper envelope of n line segments in O(n log n) time".
603:
8435:
8199:
8033:
7156:
6424:
4237:
4039:
3723:
1623:
using the same technique as normally used in Jarvis's march, but only considering the points
1235:
407:
8514:
5718:
2071:
8232:
8066:
7417:
6477:
6392:
6200:
5174:
5147:
5073:
4457:
3982:
3513:
3461:
3429:
2391:(corresponding to a partition in singleton sets). Starting from a value of 2, at iteration
1342:
1315:
1268:
983:
956:
676:
649:
194:
8606:
4229:
for the current iteration. A "squaring scheme" is used as described above in this article.
3566:(For more info, see the comments close to the corresponding part of the Chan's algorithm.)
1749:
1720:
785:
8:
8168:
7324:
341:
8801:
8655:
8635:
8545:
8415:
8148:
7793:
7469:
7444:
7136:
6768:
6671:
6646:
6626:
6606:
6586:
6457:
6372:
6270:
6250:
6180:
5744:
5698:
5678:
5653:
5589:
5564:
5539:
5510:
5490:
5429:
5053:
4737:
4609:
4548:
4434:
4212:
4090:
4065:
4014:
3962:
3942:
3922:
3897:
3749:
3698:
3678:
3649:
3629:
3544:
3488:
3328:
3270:
3250:
3222:
3202:
3182:
3156:
3136:
3109:
3089:
2715:
2394:
2374:
2354:
2260:
2240:
2220:
2162:
2097:
2051:
1980:
1957:
1937:
1917:
1818:
1798:
1778:
1700:
1526:
1369:
1295:
1111:
1030:
1010:
765:
745:
583:
456:
433:
387:
367:
321:
301:
281:
128:
70:
50:
8995:
8965:
8946:
8901:
7192:
8991:
8960:
8938:
8891:
8866:
1386:
points (listed in a clockwise or counter-clockwise order), which allows to compute
8896:
36:
8601:
4431:(Initialize an empty list (or array) to store the points of the convex hull of
2159:
The idea is to make multiple passes of the algorithm with increasing values of
2156:
time will have been spent, and the convex hull will not have been calculated.
1027:
with the lowest y coordinate, which is guaranteed to be in the convex hull of
9009:
8947:"Derandomizing an output-sensitive convex hull algorithm in three dimensions"
8853:"Optimal output-sensitive convex hull algorithms in two and three dimensions"
1471:
8030:(Jarvis march terminates when the next selected point on the convext hull,
188:
4087:(For more info, see the Jarvis march part of this algorithm below, where
3079:
739:
184:
44:
8672:
line segments, which is defined as the lower boundary of the unbounded
2257:
for which the algorithm terminates successfully may be much larger than
8890:. Lecture Notes in Computer Science. Vol. 1763. pp. 250–257.
8871:
8852:
3862:(As explained above in this article, a strategy is used where at most
2511:
iterations are made, given that the algorithm terminates once we have
261:
time. Chan's algorithm is notable because it is much simpler than the
8673:
2118:
as running it to the end would take too much time. At that moment, a
16:
Algorithm for finding the convex hull of a set of points in the plane
8921:
7626:{\displaystyle q_{i,k}:=JARVIS\_BINARY\_SEARCH(p_{i-1},p_{i},C_{k})}
1835:, we must have found the convex hull), hence the second phase takes
1697:(i.e. the points in the mini convex hulls) instead of the whole set
6114:{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}
4999:{\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}
4234:
There are other schemes: for example, the "doubling scheme", where
453:
The algorithm starts by arbitrarily partitioning the set of points
3746:
is required for this Chan's algorithm to find the convex hull of
953:. At each step in this Jarvis's march algorithm, we have a point
8798:
complexity can be achieved provided h is of polynomial order in
4884:{\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}
886:
is executed, making use of the precomputed (mini) convex hulls,
2993:
To generalize this construction for the 3-dimensional case, an
1977:
By running the two phases described above, the convex hull of
19:
8925:
1775:
times (because, in the way Jarvis march works, after at most
5810:
Hence, the total time complexity of this modified version is
3815:
and so that the time complexity of this Chan's algorithm is
5536:, its running time depends on the size of the convex hull,
2179:; each pass terminates (successfully or unsuccessfully) in
87:
points, in 2- or 3-dimensional space. The algorithm takes
4314:{\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }
3675:(These are the iterations needed to discover the value of
3453:
is used in the Jarvis march part of this Chan's algorithm,
4599:{\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }
3810:, so that not to perform too many unnecessary iterations
3287:: for instance, the point with the lowest y coordinate.)
7734:{\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}
1717:. For those points, one iteration of Jarvis's march is
8804:
8766:
8723:
8685:
8658:
8638:
8609:
8548:
8517:
8471:
8438:
8418:
8347:
8268:
8235:
8202:
8171:
8151:
8102:
8069:
8036:
7819:
7796:
7747:
7658:
7495:
7472:
7447:
7420:
7353:
7327:
7283:
7206:
7159:
7139:
7100:
7048:
6999:
6945:
6912:
6835:
6797:
6771:
6694:
6674:
6649:
6629:
6609:
6589:
6512:
6480:
6460:
6427:
6395:
6375:
6293:
6273:
6253:
6203:
6183:
6133:
6050:
6017:
5820:
5772:
5747:
5721:
5701:
5681:
5656:
5617:
5592:
5567:
5542:
5513:
5493:
5457:
5432:
5360:
5301:
5207:
5177:
5150:
5103:
5076:
5056:
5018:
4935:
4902:
4824:
4760:
4740:
4635:
4612:
4571:
4551:
4490:
4460:
4437:
4384:
4332:
4273:
4240:
4215:
4165:
4113:
4093:
4068:
4042:
4017:
3985:
3965:
3945:
3925:
3900:
3868:
3821:
3777:
3752:
3726:
3701:
3681:
3652:
3632:
3575:
3547:
3516:
3491:
3464:
3432:
3354:
3331:
3298:
3273:
3253:
3225:
3205:
3185:
3159:
3139:
3112:
3092:
3038:
2999:
2741:
2718:
2520:
2476:
2417:
2397:
2377:
2357:
2283:
2263:
2243:
2223:
2185:
2165:
2124:
2100:
2074:
2054:
2003:
1983:
1960:
1940:
1920:
1882:
1841:
1821:
1801:
1781:
1752:
1723:
1703:
1629:
1587:
1549:
1529:
1480:
1441:
1392:
1372:
1345:
1318:
1298:
1271:
1238:
1177:
1134:
1114:
1053:
1033:
1013:
986:
959:
892:
817:
788:
768:
748:
706:
679:
652:
606:
586:
519:
479:
459:
436:
410:
390:
370:
344:
324:
304:
284:
229:
197:
151:
131:
93:
73:
53:
4714:{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}:=SPLIT(P,m)}
762:
is the number of points in the subset. As there are
278:
A single pass of the algorithm requires a parameter
7191:(Angles do not need to be calculated directly: the
3646:, the number of points in the final convex hull of
1954:(see below the description of a strategy to choose
8810:
8790:
8747:
8709:
8664:
8644:
8624:
8554:
8529:
8503:
8457:
8424:
8387:
8325:
8248:
8221:
8183:
8157:
8134:
8082:
8055:
8005:
7802:
7782:
7733:
7625:
7478:
7453:
7433:
7406:
7339:
7308:
7269:
7178:
7145:
7125:
7086:
7034:
6980:
6931:
6898:
6815:
6777:
6757:
6680:
6655:
6635:
6615:
6595:
6575:
6493:
6466:
6446:
6408:
6381:
6356:
6279:
6259:
6216:
6189:
6151:
6113:
6036:
5999:
5797:
5753:
5733:
5707:
5687:
5662:
5642:
5598:
5573:
5561:(In practice, it means that Jarvis march performs
5548:
5519:
5499:
5479:
5438:
5405:
5346:
5272:
5190:
5163:
5131:
5089:
5062:
5036:
4998:
4921:
4883:
4805:
4746:
4713:
4618:
4598:
4557:
4524:
4475:
4443:
4410:
4367:
4313:
4259:
4221:
4195:
4145:
4099:
4074:
4054:
4023:
3998:
3971:
3951:
3931:
3906:
3886:
3849:
3802:
3758:
3738:
3707:
3687:
3658:
3638:
3609:
3553:
3529:
3497:
3477:
3445:
3409:
3337:
3317:
3279:
3259:
3231:
3211:
3191:
3165:
3145:
3118:
3098:
3062:
3023:
2977:
2724:
2701:
2503:
2462:
2403:
2383:
2363:
2331:
2269:
2249:
2229:
2209:
2171:
2148:
2106:
2086:
2060:
2027:
1989:
1966:
1946:
1926:
1906:
1868:
1827:
1807:
1787:
1767:
1738:
1709:
1689:
1615:
1573:
1535:
1515:
1462:
1427:
1378:
1358:
1331:
1304:
1284:
1257:
1224:
1163:
1120:
1100:
1039:
1019:
999:
972:
945:
871:
803:
774:
754:
730:
692:
665:
635:
592:
572:
505:
465:
442:
422:
396:
376:
356:
330:
310:
290:
253:
215:
175:
137:
117:
79:
59:
6643:possible next points to be on the convex hull of
6267:possible next points to be on the convex hull of
5586:At each of these iterations, it performs at most
2732:, and the total running time of the algorithm is
9007:
8937:
8755:, where h is the number of edges in the envelope
7087:{\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}
4011:(Nevertheless, this Chan's algorithm stops once
2424:
1690:{\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}
8542:(We need to start over with a higher value for
6454:is a possible next point on the convex hull of
4031:iterations of the outermost loop are performed,
2463:{\displaystyle m=\min \left(n,2^{2^{t}}\right)}
7441:is known and is a point in the convex hull of
6758:{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}
6576:{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}
6357:{\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}
1815:is the number of points in the convex hull of
8326:{\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}
7783:{\displaystyle \measuredangle p_{i-1}p_{i}z}
7728:
7665:
7035:{\displaystyle \measuredangle p_{i-1}p_{i}d}
6981:{\displaystyle \measuredangle p_{i-1}p_{i}d}
5527:is the number of points in the convex hull.)
2938:
2920:
2877:
2859:
2776:
2758:
2371:at each iteration, up to a maximum value of
2114:steps in the second phase, we interrupt the
872:{\displaystyle K\cdot O(m\log m)=O(n\log m)}
500:
486:
8979:
7790:to be the next point on the convex hull of
6177:(Note: here, a point in the convex hull of
5171:is the convex hull of the subset of points
4368:{\displaystyle {\mathcal {O}}(n\log ^{2}h)}
2038:
7407:{\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}
7126:{\displaystyle {\overrightarrow {p_{i}d}}}
5273:{\displaystyle C_{k}:=GRAHAM\_SCAN(Q_{k})}
3325:time: e.g., we can simply iterate through
2672:
2668:
2629:
2625:
2602:
2598:
2554:
2550:
1232:simply means that the next point, that is
8964:
8895:
8870:
6389:possible next points is from a different
5650:, so we do not want to perform more than
8846:
8844:
5670:iterations in the following outer loop.)
5426:algorithm to compute the convex hull of
5406:{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}
5347:{\displaystyle C_{1},C_{2},\dots ,C_{K}}
4806:{\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}
2332:{\displaystyle O(n\log m)>O(n\log h)}
1795:iterations of its outermost loop, where
18:
8885:
5132:{\displaystyle {\mathcal {O}}(m\log m)}
4196:{\displaystyle 1\leq t\leq \log \log n}
3850:{\displaystyle {\mathcal {O}}(n\log h)}
3086:algorithms to compute the convex hull,
9008:
7309:{\displaystyle {\mathcal {O}}(\log m)}
7270:{\displaystyle JARVIS\_BINARY\_SEARCH}
6899:{\displaystyle JARVIS\_BINARY\_SEARCH}
5798:{\displaystyle {\mathcal {O}}(\log m)}
5354:of respectively the subsets of points
2988:
980:in the convex hull (at the beginning,
8858:Discrete & Computational Geometry
8841:
3458:so that to compute the second point,
3410:{\displaystyle p_{1}:=PICK\_START(P)}
8850:
8196:(Note: of course, no need to return
6474:which is part of the convex hull of
2342:
2048:If an arbitrary value is chosen for
946:{\displaystyle (C_{k})_{k=1,2,...K}}
573:{\displaystyle (Q_{k})_{k=1,2,...K}}
404:are done which then terminates when
8888:Discrete and Computational Geometry
5050:(Compute the convex hull of subset
3610:{\displaystyle p_{0}:=(-\infty ,0)}
506:{\displaystyle K=\lceil n/m\rceil }
13:
8717:algorithm which can be sped up to
7881:
7872:
7857:
7554:
7533:
7392:
7286:
7246:
7225:
6875:
6854:
6088:
6053:
5970:
5928:
5900:
5854:
5823:
5775:
5606:iterations of its innermost loop.)
5507:is the number of input points and
5480:{\displaystyle {\mathcal {O}}(nh)}
5460:
5239:
5106:
4973:
4938:
4858:
4827:
4335:
4082:iterations of the outermost loop.)
3824:
3595:
3380:
3301:
1225:{\displaystyle p_{i+1}=f(p_{i},P)}
1101:{\displaystyle p_{i+1}=f(p_{i},P)}
14:
9027:
8571:
7466:in this case, it is the point of
7042:is the angle between the vectors
5643:{\displaystyle h\leq m\leq h^{2}}
5581:iterations of its outermost loop.
5295:(At this point, the convex hulls
5097:, using Graham scan, which takes
4545:(Arbitrarily split set of points
3803:{\displaystyle h\leq m\leq h^{2}}
3318:{\displaystyle {\mathcal {O}}(n)}
2712:with the logarithm taken in base
1265:, is determined as a function of
430:(see below on choosing parameter
223:), in order to obtain an optimal
4734:(Compute the convex hull of all
3894:iterations are required to find
1366:, is known and contains at most
8922:Adaptive Computational Geometry
8676:of formed by the intersections.
6765:is added to the convex hull of
6688:, only one of the points among
5532:(Given that Jarvis march is an
3959:, but it is never smaller than
673:, it computes the convex hull,
8983:Information Processing Letters
8973:
8931:
8914:
8879:
8785:
8770:
8742:
8727:
8704:
8689:
8619:
8613:
8504:{\displaystyle p_{i+1}==p_{1}}
8388:{\displaystyle ADD(C,p_{i+1})}
8382:
8357:
8320:
8275:
8135:{\displaystyle p_{i+1}==p_{1}}
8000:
7997:
7934:
7899:
7620:
7575:
7486:with the lowest y coordinate.)
7401:
7386:
7303:
7291:
6603:: that is, for each iteration
6108:
6093:
6080:
6058:
6044:, then the time complexity is
5991:
5975:
5962:
5933:
5920:
5905:
5892:
5859:
5846:
5828:
5792:
5780:
5474:
5465:
5267:
5254:
5126:
5111:
4993:
4978:
4965:
4943:
4929:, then the time complexity is
4878:
4863:
4850:
4832:
4708:
4696:
4519:
4500:
4470:
4467:
4362:
4340:
4146:{\displaystyle p_{i+1}==p_{1}}
3844:
3829:
3604:
3589:
3404:
3398:
3312:
3306:
3057:
3042:
3018:
3003:
2969:
2954:
2840:
2834:
2669:
2626:
2599:
2551:
2504:{\displaystyle O(\log \log h)}
2498:
2480:
2326:
2311:
2302:
2287:
2204:
2189:
2143:
2128:
2022:
2007:
1901:
1886:
1863:
1845:
1762:
1756:
1733:
1727:
1666:
1662:
1636:
1630:
1610:
1591:
1568:
1553:
1516:{\displaystyle f(p_{i},Q_{k})}
1510:
1484:
1457:
1445:
1428:{\displaystyle f(p_{i},Q_{k})}
1422:
1396:
1219:
1200:
1108:such that all other points of
1095:
1076:
907:
893:
866:
851:
842:
827:
811:points each, this phase takes
798:
792:
725:
710:
630:
616:
534:
520:
248:
233:
210:
201:
170:
155:
112:
97:
1:
8834:
8591:
6816:{\displaystyle 1\leq k\leq K}
6152:{\displaystyle 1\leq i\leq m}
5037:{\displaystyle 1\leq k\leq K}
3267:which is guaranteed to be in
3073:
1974:such that this is the case).
1581:time. Then, we can determine
1312:. The convex hull of the set
1128:are to the right of the line
318:(number of points of our set
8996:10.1016/0020-0190(89)90136-1
8966:10.1016/0925-7721(94)00018-Q
8897:10.1007/978-3-540-46515-7_21
4525:{\displaystyle ADD(C,p_{1})}
4411:{\displaystyle m:=2^{2^{t}}}
3771:(More specifically, we want
2347:One possible strategy is to
1474:. Hence, the computation of
1164:{\displaystyle p_{i}p_{i+1}}
1047:), and need to find a point
268:
263:Kirkpatrick–Seidel algorithm
7:
8822:
8465:has not been found so that
8145:(Return the convex hull of
6037:{\displaystyle m\leq h^{2}}
4922:{\displaystyle m\leq h^{2}}
3887:{\displaystyle \log \log n}
3219:points, the convex hull of
2277:, and produce a complexity
1869:{\displaystyle O(Kh\log m)}
273:
10:
9032:
8791:{\displaystyle O(n\log h)}
8748:{\displaystyle O(n\log h)}
8710:{\displaystyle O(n\log n)}
7741:which maximizes the angle
6932:{\displaystyle d\in C_{k}}
6197:is already known, that is
5534:output-sensitive algorithm
5451:(Jarvis march performs in
3695:, which is an estimate of
3063:{\displaystyle O(n\log h)}
3024:{\displaystyle O(n\log n)}
2210:{\displaystyle O(n\log m)}
2149:{\displaystyle O(n\log m)}
2028:{\displaystyle O(n\log h)}
1907:{\displaystyle O(n\log h)}
1616:{\displaystyle f(p_{i},P)}
1574:{\displaystyle O(K\log m)}
731:{\displaystyle O(p\log p)}
254:{\displaystyle O(n\log h)}
176:{\displaystyle O(n\log n)}
118:{\displaystyle O(n\log h)}
41:output-sensitive algorithm
8851:Chan, Timothy M. (1996).
6668:(Note: at each iteration
2470:is chosen. In that case,
1463:{\displaystyle O(\log m)}
882:During the second phase,
600:points each; notice that
8063:, is the initial point,
7321:(Note: at the iteration
3485:, in the convex hull of
738:algorithm (for example,
636:{\displaystyle K=O(n/m)}
8458:{\displaystyle p_{i+1}}
8222:{\displaystyle p_{i+1}}
8056:{\displaystyle p_{i+1}}
7179:{\displaystyle q_{i,k}}
6447:{\displaystyle q_{i,k}}
4260:{\displaystyle m=2^{t}}
4055:{\displaystyle m\neq h}
3739:{\displaystyle h\leq m}
2039:Choosing the parameter
1543:subsets can be done in
1258:{\displaystyle p_{i+1}}
423:{\displaystyle m\geq h}
298:which is between 0 and
9016:Convex hull algorithms
8952:Computational Geometry
8829:Convex hull algorithms
8812:
8792:
8749:
8711:
8666:
8646:
8626:
8556:
8531:
8530:{\displaystyle m<h}
8505:
8459:
8426:
8389:
8327:
8250:
8223:
8185:
8159:
8136:
8084:
8057:
8007:
7804:
7784:
7735:
7627:
7480:
7455:
7435:
7408:
7341:
7310:
7271:
7180:
7147:
7127:
7088:
7036:
6982:
6933:
6900:
6817:
6779:
6759:
6682:
6657:
6637:
6617:
6597:
6577:
6495:
6468:
6448:
6410:
6383:
6358:
6281:
6261:
6218:
6191:
6153:
6115:
6038:
6001:
5799:
5755:
5735:
5734:{\displaystyle m<h}
5709:
5689:
5664:
5644:
5600:
5575:
5550:
5521:
5501:
5481:
5440:
5407:
5348:
5274:
5192:
5165:
5133:
5091:
5064:
5038:
5000:
4923:
4885:
4807:
4748:
4715:
4620:
4600:
4559:
4526:
4477:
4445:
4412:
4369:
4315:
4261:
4223:
4197:
4147:
4101:
4076:
4056:
4025:
4000:
3973:
3953:
3933:
3908:
3888:
3851:
3804:
3760:
3740:
3709:
3689:
3660:
3640:
3611:
3555:
3531:
3499:
3479:
3447:
3411:
3339:
3319:
3292:(This operation takes
3281:
3261:
3233:
3213:
3193:
3167:
3147:
3120:
3106:, of a set of points,
3100:
3064:
3025:
2979:
2881:
2780:
2726:
2703:
2505:
2464:
2405:
2385:
2365:
2333:
2271:
2251:
2231:
2211:
2173:
2150:
2108:
2094:. In that case, after
2088:
2087:{\displaystyle m<h}
2062:
2029:
1997:points is computed in
1991:
1968:
1948:
1928:
1908:
1870:
1829:
1809:
1789:
1769:
1740:
1711:
1691:
1617:
1575:
1537:
1517:
1464:
1429:
1380:
1360:
1333:
1306:
1286:
1259:
1226:
1165:
1122:
1102:
1041:
1021:
1001:
974:
947:
873:
805:
776:
756:
732:
694:
667:
637:
594:
574:
507:
467:
444:
424:
398:
378:
358:
332:
312:
292:
255:
217:
177:
139:
119:
81:
61:
29:computational geometry
24:
8813:
8793:
8750:
8712:
8667:
8647:
8627:
8557:
8532:
8506:
8460:
8427:
8390:
8328:
8251:
8249:{\displaystyle p_{1}}
8224:
8186:
8160:
8137:
8085:
8083:{\displaystyle p_{1}}
8058:
8008:
7805:
7785:
7736:
7628:
7481:
7456:
7436:
7434:{\displaystyle p_{1}}
7409:
7342:
7311:
7272:
7181:
7148:
7128:
7089:
7037:
6983:
6934:
6901:
6818:
6780:
6760:
6683:
6658:
6638:
6618:
6598:
6578:
6496:
6494:{\displaystyle C_{k}}
6469:
6449:
6411:
6409:{\displaystyle C_{k}}
6384:
6359:
6282:
6262:
6219:
6217:{\displaystyle p_{1}}
6192:
6154:
6116:
6039:
6002:
5800:
5756:
5741:, the convex hull of
5736:
5710:
5690:
5665:
5645:
5601:
5576:
5551:
5522:
5502:
5482:
5441:
5408:
5349:
5275:
5193:
5191:{\displaystyle Q_{k}}
5166:
5164:{\displaystyle C_{k}}
5134:
5092:
5090:{\displaystyle Q_{k}}
5065:
5039:
5001:
4924:
4886:
4808:
4749:
4716:
4621:
4601:
4560:
4527:
4478:
4476:{\displaystyle C:=()}
4451:, as they are found.)
4446:
4413:
4370:
4316:
4262:
4224:
4198:
4148:
4102:
4077:
4062:, it doesn't perform
4057:
4026:
4001:
3999:{\displaystyle h^{2}}
3974:
3954:
3934:
3909:
3889:
3852:
3805:
3761:
3741:
3710:
3690:
3661:
3641:
3612:
3556:
3532:
3530:{\displaystyle p_{0}}
3500:
3480:
3478:{\displaystyle p_{2}}
3448:
3446:{\displaystyle p_{0}}
3412:
3340:
3320:
3282:
3262:
3234:
3214:
3194:
3168:
3148:
3121:
3101:
3065:
3026:
2980:
2843:
2742:
2727:
2704:
2506:
2465:
2406:
2386:
2366:
2334:
2272:
2252:
2232:
2212:
2174:
2151:
2109:
2089:
2068:, it may happen that
2063:
2030:
1992:
1969:
1949:
1929:
1909:
1871:
1830:
1810:
1790:
1770:
1741:
1712:
1692:
1618:
1576:
1538:
1518:
1465:
1430:
1381:
1361:
1359:{\displaystyle C_{k}}
1334:
1332:{\displaystyle Q_{k}}
1307:
1287:
1285:{\displaystyle p_{i}}
1260:
1227:
1171:, where the notation
1166:
1123:
1103:
1042:
1022:
1002:
1000:{\displaystyle p_{i}}
975:
973:{\displaystyle p_{i}}
948:
874:
806:
777:
757:
733:
695:
693:{\displaystyle C_{k}}
668:
666:{\displaystyle Q_{k}}
638:
595:
575:
508:
468:
445:
425:
399:
379:
359:
333:
313:
293:
256:
218:
216:{\displaystyle O(nh)}
178:
140:
120:
82:
62:
22:
8802:
8764:
8721:
8683:
8679:Hershberger gave an
8656:
8636:
8625:{\displaystyle L(S)}
8607:
8546:
8515:
8469:
8436:
8416:
8345:
8266:
8233:
8200:
8169:
8149:
8100:
8067:
8034:
7817:
7794:
7745:
7656:
7493:
7470:
7445:
7418:
7351:
7325:
7281:
7277:can be performed in
7204:
7157:
7137:
7098:
7046:
6997:
6943:
6939:such that the angle
6910:
6833:
6795:
6769:
6692:
6672:
6647:
6627:
6607:
6587:
6510:
6478:
6458:
6425:
6393:
6373:
6291:
6271:
6251:
6201:
6181:
6131:
6048:
6015:
5818:
5770:
5745:
5719:
5699:
5679:
5654:
5615:
5590:
5565:
5540:
5511:
5491:
5455:
5430:
5413:have been computed.)
5358:
5299:
5205:
5175:
5148:
5101:
5074:
5054:
5016:
4933:
4900:
4822:
4758:
4738:
4633:
4610:
4569:
4549:
4488:
4458:
4435:
4382:
4330:
4271:
4238:
4213:
4163:
4111:
4091:
4066:
4040:
4015:
3983:
3963:
3943:
3939:may not be equal to
3923:
3898:
3866:
3819:
3775:
3750:
3724:
3699:
3679:
3650:
3630:
3573:
3545:
3514:
3489:
3462:
3430:
3352:
3329:
3296:
3271:
3251:
3223:
3203:
3183:
3157:
3137:
3110:
3090:
3036:
2997:
2739:
2716:
2518:
2474:
2415:
2395:
2375:
2355:
2281:
2261:
2241:
2221:
2183:
2163:
2122:
2098:
2072:
2052:
2001:
1981:
1958:
1938:
1918:
1880:
1876:time, equivalent to
1839:
1819:
1799:
1779:
1768:{\displaystyle O(h)}
1750:
1739:{\displaystyle O(K)}
1721:
1701:
1627:
1585:
1547:
1527:
1478:
1439:
1390:
1370:
1343:
1316:
1296:
1269:
1236:
1175:
1132:
1112:
1051:
1031:
1011:
1007:may be the point in
984:
957:
890:
815:
804:{\displaystyle O(m)}
786:
766:
746:
704:
677:
650:
604:
584:
517:
477:
457:
434:
408:
388:
368:
342:
322:
302:
282:
227:
195:
187:, for example) with
149:
129:
91:
71:
51:
8432:iterations a point
8184:{\displaystyle i=h}
7340:{\displaystyle i=1}
4754:subsets of points,
4606:subsets of roughly
2989:In three dimensions
357:{\displaystyle m=h}
8872:10.1007/BF02712873
8808:
8788:
8745:
8707:
8662:
8642:
8622:
8552:
8527:
8501:
8455:
8422:
8385:
8323:
8246:
8229:which is equal to
8219:
8181:
8155:
8132:
8080:
8053:
8003:
7800:
7780:
7731:
7652:(Choose the point
7623:
7476:
7451:
7431:
7404:
7337:
7306:
7267:
7176:
7143:
7123:
7084:
7032:
6978:
6929:
6896:
6813:
6775:
6755:
6678:
6653:
6633:
6613:
6593:
6573:
6491:
6464:
6444:
6406:
6379:
6354:
6277:
6257:
6214:
6187:
6149:
6111:
6034:
5997:
5795:
5751:
5731:
5705:
5685:
5660:
5640:
5596:
5571:
5546:
5517:
5497:
5477:
5436:
5403:
5344:
5270:
5188:
5161:
5129:
5087:
5060:
5034:
4996:
4919:
4881:
4803:
4744:
4711:
4616:
4596:
4555:
4522:
4473:
4441:
4408:
4365:
4311:
4257:
4219:
4193:
4143:
4097:
4072:
4052:
4021:
3996:
3969:
3949:
3929:
3904:
3884:
3847:
3800:
3756:
3736:
3705:
3685:
3656:
3636:
3607:
3551:
3527:
3495:
3475:
3443:
3407:
3335:
3315:
3277:
3257:
3229:
3209:
3189:
3163:
3143:
3116:
3096:
3060:
3021:
2975:
2722:
2699:
2501:
2460:
2401:
2381:
2361:
2329:
2267:
2247:
2227:
2207:
2169:
2146:
2104:
2084:
2058:
2025:
1987:
1964:
1944:
1924:
1904:
1866:
1825:
1805:
1785:
1765:
1736:
1707:
1687:
1613:
1571:
1533:
1513:
1460:
1425:
1376:
1356:
1329:
1302:
1282:
1255:
1222:
1161:
1118:
1098:
1037:
1017:
997:
970:
943:
869:
801:
772:
752:
728:
690:
663:
633:
590:
570:
503:
463:
440:
420:
394:
374:
354:
328:
308:
288:
251:
213:
173:
135:
115:
77:
57:
25:
8939:Chazelle, Bernard
8924:". Ph.D. thesis,
8907:978-3-540-67181-7
8811:{\displaystyle n}
8665:{\displaystyle n}
8645:{\displaystyle S}
8555:{\displaystyle m}
8425:{\displaystyle m}
8158:{\displaystyle P}
7803:{\displaystyle P}
7479:{\displaystyle P}
7454:{\displaystyle P}
7146:{\displaystyle d}
7121:
7082:
6778:{\displaystyle P}
6681:{\displaystyle i}
6656:{\displaystyle P}
6636:{\displaystyle K}
6616:{\displaystyle i}
6596:{\displaystyle i}
6467:{\displaystyle P}
6382:{\displaystyle K}
6280:{\displaystyle P}
6260:{\displaystyle K}
6190:{\displaystyle P}
5877:
5761:cannot be found.)
5754:{\displaystyle P}
5708:{\displaystyle h}
5688:{\displaystyle m}
5663:{\displaystyle m}
5599:{\displaystyle n}
5574:{\displaystyle h}
5549:{\displaystyle h}
5520:{\displaystyle h}
5500:{\displaystyle n}
5439:{\displaystyle P}
5063:{\displaystyle k}
4747:{\displaystyle K}
4619:{\displaystyle m}
4590:
4558:{\displaystyle P}
4444:{\displaystyle P}
4222:{\displaystyle m}
4100:{\displaystyle C}
4075:{\displaystyle m}
4036:that is, even if
4024:{\displaystyle h}
3979:and greater than
3972:{\displaystyle h}
3952:{\displaystyle h}
3932:{\displaystyle m}
3919:(Note: the final
3907:{\displaystyle m}
3759:{\displaystyle P}
3708:{\displaystyle h}
3688:{\displaystyle m}
3659:{\displaystyle P}
3639:{\displaystyle h}
3554:{\displaystyle P}
3498:{\displaystyle P}
3338:{\displaystyle P}
3280:{\displaystyle C}
3260:{\displaystyle P}
3247:(Pick a point of
3232:{\displaystyle P}
3212:{\displaystyle h}
3192:{\displaystyle C}
3166:{\displaystyle n}
3146:{\displaystyle P}
3119:{\displaystyle P}
3099:{\displaystyle C}
2725:{\displaystyle 2}
2404:{\displaystyle t}
2384:{\displaystyle n}
2364:{\displaystyle m}
2343:Squaring Strategy
2270:{\displaystyle h}
2250:{\displaystyle m}
2230:{\displaystyle m}
2172:{\displaystyle m}
2107:{\displaystyle m}
2061:{\displaystyle m}
1990:{\displaystyle n}
1967:{\displaystyle m}
1947:{\displaystyle h}
1927:{\displaystyle m}
1828:{\displaystyle P}
1808:{\displaystyle h}
1788:{\displaystyle h}
1710:{\displaystyle P}
1536:{\displaystyle K}
1379:{\displaystyle m}
1305:{\displaystyle P}
1121:{\displaystyle P}
1040:{\displaystyle P}
1020:{\displaystyle P}
775:{\displaystyle K}
755:{\displaystyle p}
593:{\displaystyle m}
466:{\displaystyle P}
443:{\displaystyle m}
397:{\displaystyle m}
377:{\displaystyle h}
331:{\displaystyle P}
311:{\displaystyle n}
291:{\displaystyle m}
138:{\displaystyle h}
80:{\displaystyle n}
60:{\displaystyle P}
9023:
9000:
8999:
8977:
8971:
8970:
8968:
8935:
8929:
8920:Frank Nielsen. "
8918:
8912:
8911:
8899:
8883:
8877:
8876:
8874:
8848:
8817:
8815:
8814:
8809:
8797:
8795:
8794:
8789:
8754:
8752:
8751:
8746:
8716:
8714:
8713:
8708:
8671:
8669:
8668:
8663:
8651:
8649:
8648:
8643:
8631:
8629:
8628:
8623:
8561:
8559:
8558:
8553:
8536:
8534:
8533:
8528:
8510:
8508:
8507:
8502:
8500:
8499:
8487:
8486:
8464:
8462:
8461:
8456:
8454:
8453:
8431:
8429:
8428:
8423:
8394:
8392:
8391:
8386:
8381:
8380:
8332:
8330:
8329:
8324:
8319:
8318:
8300:
8299:
8287:
8286:
8255:
8253:
8252:
8247:
8245:
8244:
8228:
8226:
8225:
8220:
8218:
8217:
8190:
8188:
8187:
8182:
8164:
8162:
8161:
8156:
8141:
8139:
8138:
8133:
8131:
8130:
8118:
8117:
8089:
8087:
8086:
8081:
8079:
8078:
8062:
8060:
8059:
8054:
8052:
8051:
8012:
8010:
8009:
8004:
7996:
7995:
7971:
7970:
7952:
7951:
7930:
7929:
7917:
7916:
7835:
7834:
7809:
7807:
7806:
7801:
7789:
7787:
7786:
7781:
7776:
7775:
7766:
7765:
7740:
7738:
7737:
7732:
7727:
7726:
7702:
7701:
7683:
7682:
7632:
7630:
7629:
7624:
7619:
7618:
7606:
7605:
7593:
7592:
7511:
7510:
7485:
7483:
7482:
7477:
7460:
7458:
7457:
7452:
7440:
7438:
7437:
7432:
7430:
7429:
7413:
7411:
7410:
7405:
7382:
7381:
7369:
7368:
7346:
7344:
7343:
7338:
7315:
7313:
7312:
7307:
7290:
7289:
7276:
7274:
7273:
7268:
7193:orientation test
7185:
7183:
7182:
7177:
7175:
7174:
7152:
7150:
7149:
7144:
7132:
7130:
7129:
7124:
7122:
7117:
7113:
7112:
7102:
7093:
7091:
7090:
7085:
7083:
7078:
7077:
7076:
7061:
7060:
7050:
7041:
7039:
7038:
7033:
7028:
7027:
7018:
7017:
6987:
6985:
6984:
6979:
6974:
6973:
6964:
6963:
6938:
6936:
6935:
6930:
6928:
6927:
6906:finds the point
6905:
6903:
6902:
6897:
6822:
6820:
6819:
6814:
6784:
6782:
6781:
6776:
6764:
6762:
6761:
6756:
6754:
6753:
6729:
6728:
6710:
6709:
6687:
6685:
6684:
6679:
6662:
6660:
6659:
6654:
6642:
6640:
6639:
6634:
6622:
6620:
6619:
6614:
6602:
6600:
6599:
6594:
6582:
6580:
6579:
6574:
6572:
6571:
6547:
6546:
6528:
6527:
6500:
6498:
6497:
6492:
6490:
6489:
6473:
6471:
6470:
6465:
6453:
6451:
6450:
6445:
6443:
6442:
6415:
6413:
6412:
6407:
6405:
6404:
6388:
6386:
6385:
6380:
6364:, are computed.)
6363:
6361:
6360:
6355:
6353:
6352:
6328:
6327:
6309:
6308:
6286:
6284:
6283:
6278:
6266:
6264:
6263:
6258:
6223:
6221:
6220:
6215:
6213:
6212:
6196:
6194:
6193:
6188:
6158:
6156:
6155:
6150:
6120:
6118:
6117:
6112:
6092:
6091:
6079:
6078:
6057:
6056:
6043:
6041:
6040:
6035:
6033:
6032:
6006:
6004:
6003:
5998:
5990:
5989:
5974:
5973:
5961:
5960:
5959:
5958:
5932:
5931:
5904:
5903:
5882:
5878:
5870:
5858:
5857:
5827:
5826:
5804:
5802:
5801:
5796:
5779:
5778:
5760:
5758:
5757:
5752:
5740:
5738:
5737:
5732:
5714:
5712:
5711:
5706:
5695:is smaller than
5694:
5692:
5691:
5686:
5675:(If the current
5669:
5667:
5666:
5661:
5649:
5647:
5646:
5641:
5639:
5638:
5605:
5603:
5602:
5597:
5580:
5578:
5577:
5572:
5555:
5553:
5552:
5547:
5526:
5524:
5523:
5518:
5506:
5504:
5503:
5498:
5486:
5484:
5483:
5478:
5464:
5463:
5445:
5443:
5442:
5437:
5420:modified version
5412:
5410:
5409:
5404:
5402:
5401:
5383:
5382:
5370:
5369:
5353:
5351:
5350:
5345:
5343:
5342:
5324:
5323:
5311:
5310:
5279:
5277:
5276:
5271:
5266:
5265:
5217:
5216:
5197:
5195:
5194:
5189:
5187:
5186:
5170:
5168:
5167:
5162:
5160:
5159:
5138:
5136:
5135:
5130:
5110:
5109:
5096:
5094:
5093:
5088:
5086:
5085:
5069:
5067:
5066:
5061:
5043:
5041:
5040:
5035:
5005:
5003:
5002:
4997:
4977:
4976:
4964:
4963:
4942:
4941:
4928:
4926:
4925:
4920:
4918:
4917:
4890:
4888:
4887:
4882:
4862:
4861:
4831:
4830:
4812:
4810:
4809:
4804:
4802:
4801:
4783:
4782:
4770:
4769:
4753:
4751:
4750:
4745:
4720:
4718:
4717:
4712:
4677:
4676:
4658:
4657:
4645:
4644:
4625:
4623:
4622:
4617:
4605:
4603:
4602:
4597:
4595:
4591:
4583:
4564:
4562:
4561:
4556:
4531:
4529:
4528:
4523:
4518:
4517:
4482:
4480:
4479:
4474:
4450:
4448:
4447:
4442:
4417:
4415:
4414:
4409:
4407:
4406:
4405:
4404:
4374:
4372:
4371:
4366:
4355:
4354:
4339:
4338:
4320:
4318:
4317:
4312:
4310:
4306:
4266:
4264:
4263:
4258:
4256:
4255:
4228:
4226:
4225:
4220:
4202:
4200:
4199:
4194:
4152:
4150:
4149:
4144:
4142:
4141:
4129:
4128:
4106:
4104:
4103:
4098:
4081:
4079:
4078:
4073:
4061:
4059:
4058:
4053:
4030:
4028:
4027:
4022:
4005:
4003:
4002:
3997:
3995:
3994:
3978:
3976:
3975:
3970:
3958:
3956:
3955:
3950:
3938:
3936:
3935:
3930:
3913:
3911:
3910:
3905:
3893:
3891:
3890:
3885:
3856:
3854:
3853:
3848:
3828:
3827:
3809:
3807:
3806:
3801:
3799:
3798:
3765:
3763:
3762:
3757:
3745:
3743:
3742:
3737:
3714:
3712:
3711:
3706:
3694:
3692:
3691:
3686:
3665:
3663:
3662:
3657:
3645:
3643:
3642:
3637:
3616:
3614:
3613:
3608:
3585:
3584:
3560:
3558:
3557:
3552:
3536:
3534:
3533:
3528:
3526:
3525:
3504:
3502:
3501:
3496:
3484:
3482:
3481:
3476:
3474:
3473:
3452:
3450:
3449:
3444:
3442:
3441:
3416:
3414:
3413:
3408:
3364:
3363:
3344:
3342:
3341:
3336:
3324:
3322:
3321:
3316:
3305:
3304:
3286:
3284:
3283:
3278:
3266:
3264:
3263:
3258:
3238:
3236:
3235:
3230:
3218:
3216:
3215:
3210:
3198:
3196:
3195:
3190:
3172:
3170:
3169:
3164:
3152:
3150:
3149:
3144:
3125:
3123:
3122:
3117:
3105:
3103:
3102:
3097:
3069:
3067:
3066:
3061:
3030:
3028:
3027:
3022:
2984:
2982:
2981:
2976:
2947:
2943:
2942:
2941:
2891:
2890:
2880:
2857:
2827:
2823:
2822:
2818:
2817:
2816:
2815:
2779:
2756:
2731:
2729:
2728:
2723:
2708:
2706:
2705:
2700:
2695:
2667:
2647:
2646:
2645:
2612:
2611:
2585:
2581:
2580:
2579:
2578:
2543:
2542:
2541:
2540:
2510:
2508:
2507:
2502:
2469:
2467:
2466:
2461:
2459:
2455:
2454:
2453:
2452:
2451:
2410:
2408:
2407:
2402:
2390:
2388:
2387:
2382:
2370:
2368:
2367:
2362:
2338:
2336:
2335:
2330:
2276:
2274:
2273:
2268:
2256:
2254:
2253:
2248:
2236:
2234:
2233:
2228:
2216:
2214:
2213:
2208:
2178:
2176:
2175:
2170:
2155:
2153:
2152:
2147:
2113:
2111:
2110:
2105:
2093:
2091:
2090:
2085:
2067:
2065:
2064:
2059:
2044:
2034:
2032:
2031:
2026:
1996:
1994:
1993:
1988:
1973:
1971:
1970:
1965:
1953:
1951:
1950:
1945:
1933:
1931:
1930:
1925:
1913:
1911:
1910:
1905:
1875:
1873:
1872:
1867:
1834:
1832:
1831:
1826:
1814:
1812:
1811:
1806:
1794:
1792:
1791:
1786:
1774:
1772:
1771:
1766:
1745:
1743:
1742:
1737:
1716:
1714:
1713:
1708:
1696:
1694:
1693:
1688:
1686:
1685:
1661:
1660:
1648:
1647:
1622:
1620:
1619:
1614:
1603:
1602:
1580:
1578:
1577:
1572:
1542:
1540:
1539:
1534:
1522:
1520:
1519:
1514:
1509:
1508:
1496:
1495:
1469:
1467:
1466:
1461:
1434:
1432:
1431:
1426:
1421:
1420:
1408:
1407:
1385:
1383:
1382:
1377:
1365:
1363:
1362:
1357:
1355:
1354:
1338:
1336:
1335:
1330:
1328:
1327:
1311:
1309:
1308:
1303:
1291:
1289:
1288:
1283:
1281:
1280:
1264:
1262:
1261:
1256:
1254:
1253:
1231:
1229:
1228:
1223:
1212:
1211:
1193:
1192:
1170:
1168:
1167:
1162:
1160:
1159:
1144:
1143:
1127:
1125:
1124:
1119:
1107:
1105:
1104:
1099:
1088:
1087:
1069:
1068:
1046:
1044:
1043:
1038:
1026:
1024:
1023:
1018:
1006:
1004:
1003:
998:
996:
995:
979:
977:
976:
971:
969:
968:
952:
950:
949:
944:
942:
941:
905:
904:
878:
876:
875:
870:
810:
808:
807:
802:
781:
779:
778:
773:
761:
759:
758:
753:
737:
735:
734:
729:
699:
697:
696:
691:
689:
688:
672:
670:
669:
664:
662:
661:
646:For each subset
642:
640:
639:
634:
626:
599:
597:
596:
591:
579:
577:
576:
571:
569:
568:
532:
531:
512:
510:
509:
504:
496:
472:
470:
469:
464:
449:
447:
446:
441:
429:
427:
426:
421:
403:
401:
400:
395:
383:
381:
380:
375:
363:
361:
360:
355:
337:
335:
334:
329:
317:
315:
314:
309:
297:
295:
294:
289:
260:
258:
257:
252:
222:
220:
219:
214:
182:
180:
179:
174:
144:
142:
141:
136:
124:
122:
121:
116:
86:
84:
83:
78:
66:
64:
63:
58:
39:, is an optimal
33:Chan's algorithm
9031:
9030:
9026:
9025:
9024:
9022:
9021:
9020:
9006:
9005:
9004:
9003:
8978:
8974:
8936:
8932:
8919:
8915:
8908:
8884:
8880:
8849:
8842:
8837:
8825:
8803:
8800:
8799:
8765:
8762:
8761:
8722:
8719:
8718:
8684:
8681:
8680:
8657:
8654:
8653:
8637:
8634:
8633:
8608:
8605:
8604:
8594:
8574:
8547:
8544:
8543:
8516:
8513:
8512:
8495:
8491:
8476:
8472:
8470:
8467:
8466:
8443:
8439:
8437:
8434:
8433:
8417:
8414:
8413:
8370:
8366:
8346:
8343:
8342:
8314:
8310:
8295:
8291:
8282:
8278:
8267:
8264:
8263:
8240:
8236:
8234:
8231:
8230:
8207:
8203:
8201:
8198:
8197:
8170:
8167:
8166:
8165:which contains
8150:
8147:
8146:
8126:
8122:
8107:
8103:
8101:
8098:
8097:
8074:
8070:
8068:
8065:
8064:
8041:
8037:
8035:
8032:
8031:
7985:
7981:
7960:
7956:
7941:
7937:
7925:
7921:
7906:
7902:
7824:
7820:
7818:
7815:
7814:
7795:
7792:
7791:
7771:
7767:
7755:
7751:
7746:
7743:
7742:
7716:
7712:
7691:
7687:
7672:
7668:
7657:
7654:
7653:
7614:
7610:
7601:
7597:
7582:
7578:
7500:
7496:
7494:
7491:
7490:
7471:
7468:
7467:
7446:
7443:
7442:
7425:
7421:
7419:
7416:
7415:
7377:
7373:
7358:
7354:
7352:
7349:
7348:
7326:
7323:
7322:
7285:
7284:
7282:
7279:
7278:
7205:
7202:
7201:
7164:
7160:
7158:
7155:
7154:
7138:
7135:
7134:
7108:
7104:
7103:
7101:
7099:
7096:
7095:
7066:
7062:
7056:
7052:
7051:
7049:
7047:
7044:
7043:
7023:
7019:
7007:
7003:
6998:
6995:
6994:
6969:
6965:
6953:
6949:
6944:
6941:
6940:
6923:
6919:
6911:
6908:
6907:
6834:
6831:
6830:
6796:
6793:
6792:
6770:
6767:
6766:
6743:
6739:
6718:
6714:
6699:
6695:
6693:
6690:
6689:
6673:
6670:
6669:
6648:
6645:
6644:
6628:
6625:
6624:
6608:
6605:
6604:
6588:
6585:
6584:
6561:
6557:
6536:
6532:
6517:
6513:
6511:
6508:
6507:
6485:
6481:
6479:
6476:
6475:
6459:
6456:
6455:
6432:
6428:
6426:
6423:
6422:
6400:
6396:
6394:
6391:
6390:
6374:
6371:
6370:
6369:(Each of these
6342:
6338:
6317:
6313:
6298:
6294:
6292:
6289:
6288:
6272:
6269:
6268:
6252:
6249:
6248:
6243:(In this inner
6208:
6204:
6202:
6199:
6198:
6182:
6179:
6178:
6132:
6129:
6128:
6087:
6086:
6074:
6070:
6052:
6051:
6049:
6046:
6045:
6028:
6024:
6016:
6013:
6012:
5985:
5981:
5969:
5968:
5954:
5950:
5949:
5945:
5927:
5926:
5899:
5898:
5869:
5865:
5853:
5852:
5822:
5821:
5819:
5816:
5815:
5774:
5773:
5771:
5768:
5767:
5746:
5743:
5742:
5720:
5717:
5716:
5700:
5697:
5696:
5680:
5677:
5676:
5655:
5652:
5651:
5634:
5630:
5616:
5613:
5612:
5591:
5588:
5587:
5566:
5563:
5562:
5541:
5538:
5537:
5512:
5509:
5508:
5492:
5489:
5488:
5459:
5458:
5456:
5453:
5452:
5431:
5428:
5427:
5397:
5393:
5378:
5374:
5365:
5361:
5359:
5356:
5355:
5338:
5334:
5319:
5315:
5306:
5302:
5300:
5297:
5296:
5261:
5257:
5212:
5208:
5206:
5203:
5202:
5182:
5178:
5176:
5173:
5172:
5155:
5151:
5149:
5146:
5145:
5105:
5104:
5102:
5099:
5098:
5081:
5077:
5075:
5072:
5071:
5055:
5052:
5051:
5017:
5014:
5013:
4972:
4971:
4959:
4955:
4937:
4936:
4934:
4931:
4930:
4913:
4909:
4901:
4898:
4897:
4857:
4856:
4826:
4825:
4823:
4820:
4819:
4797:
4793:
4778:
4774:
4765:
4761:
4759:
4756:
4755:
4739:
4736:
4735:
4672:
4668:
4653:
4649:
4640:
4636:
4634:
4631:
4630:
4626:elements each.)
4611:
4608:
4607:
4582:
4578:
4570:
4567:
4566:
4550:
4547:
4546:
4513:
4509:
4489:
4486:
4485:
4459:
4456:
4455:
4436:
4433:
4432:
4400:
4396:
4395:
4391:
4383:
4380:
4379:
4350:
4346:
4334:
4333:
4331:
4328:
4327:
4296:
4292:
4272:
4269:
4268:
4251:
4247:
4239:
4236:
4235:
4214:
4211:
4210:
4209:(Set parameter
4164:
4161:
4160:
4137:
4133:
4118:
4114:
4112:
4109:
4108:
4107:is returned if
4092:
4089:
4088:
4067:
4064:
4063:
4041:
4038:
4037:
4016:
4013:
4012:
3990:
3986:
3984:
3981:
3980:
3964:
3961:
3960:
3944:
3941:
3940:
3924:
3921:
3920:
3899:
3896:
3895:
3867:
3864:
3863:
3823:
3822:
3820:
3817:
3816:
3794:
3790:
3776:
3773:
3772:
3751:
3748:
3747:
3725:
3722:
3721:
3700:
3697:
3696:
3680:
3677:
3676:
3651:
3648:
3647:
3631:
3628:
3627:
3580:
3576:
3574:
3571:
3570:
3546:
3543:
3542:
3521:
3517:
3515:
3512:
3511:
3490:
3487:
3486:
3469:
3465:
3463:
3460:
3459:
3437:
3433:
3431:
3428:
3427:
3359:
3355:
3353:
3350:
3349:
3330:
3327:
3326:
3300:
3299:
3297:
3294:
3293:
3272:
3269:
3268:
3252:
3249:
3248:
3224:
3221:
3220:
3204:
3201:
3200:
3184:
3181:
3180:
3158:
3155:
3154:
3138:
3135:
3134:
3111:
3108:
3107:
3091:
3088:
3087:
3076:
3037:
3034:
3033:
2998:
2995:
2994:
2991:
2913:
2909:
2902:
2898:
2886:
2882:
2858:
2847:
2811:
2807:
2806:
2802:
2798:
2788:
2784:
2757:
2746:
2740:
2737:
2736:
2717:
2714:
2713:
2685:
2657:
2641:
2637:
2636:
2607:
2603:
2574:
2570:
2569:
2565:
2561:
2536:
2532:
2531:
2527:
2519:
2516:
2515:
2475:
2472:
2471:
2447:
2443:
2442:
2438:
2431:
2427:
2416:
2413:
2412:
2396:
2393:
2392:
2376:
2373:
2372:
2356:
2353:
2352:
2345:
2282:
2279:
2278:
2262:
2259:
2258:
2242:
2239:
2238:
2222:
2219:
2218:
2184:
2181:
2180:
2164:
2161:
2160:
2123:
2120:
2119:
2099:
2096:
2095:
2073:
2070:
2069:
2053:
2050:
2049:
2046:
2040:
2002:
1999:
1998:
1982:
1979:
1978:
1959:
1956:
1955:
1939:
1936:
1935:
1919:
1916:
1915:
1881:
1878:
1877:
1840:
1837:
1836:
1820:
1817:
1816:
1800:
1797:
1796:
1780:
1777:
1776:
1751:
1748:
1747:
1722:
1719:
1718:
1702:
1699:
1698:
1669:
1665:
1656:
1652:
1643:
1639:
1628:
1625:
1624:
1598:
1594:
1586:
1583:
1582:
1548:
1545:
1544:
1528:
1525:
1524:
1504:
1500:
1491:
1487:
1479:
1476:
1475:
1440:
1437:
1436:
1416:
1412:
1403:
1399:
1391:
1388:
1387:
1371:
1368:
1367:
1350:
1346:
1344:
1341:
1340:
1323:
1319:
1317:
1314:
1313:
1297:
1294:
1293:
1276:
1272:
1270:
1267:
1266:
1243:
1239:
1237:
1234:
1233:
1207:
1203:
1182:
1178:
1176:
1173:
1172:
1149:
1145:
1139:
1135:
1133:
1130:
1129:
1113:
1110:
1109:
1083:
1079:
1058:
1054:
1052:
1049:
1048:
1032:
1029:
1028:
1012:
1009:
1008:
991:
987:
985:
982:
981:
964:
960:
958:
955:
954:
910:
906:
900:
896:
891:
888:
887:
816:
813:
812:
787:
784:
783:
767:
764:
763:
747:
744:
743:
705:
702:
701:
684:
680:
678:
675:
674:
657:
653:
651:
648:
647:
622:
605:
602:
601:
585:
582:
581:
537:
533:
527:
523:
518:
515:
514:
492:
478:
475:
474:
458:
455:
454:
435:
432:
431:
409:
406:
405:
389:
386:
385:
369:
366:
365:
343:
340:
339:
323:
320:
319:
303:
300:
299:
283:
280:
279:
276:
271:
228:
225:
224:
196:
193:
192:
150:
147:
146:
130:
127:
126:
92:
89:
88:
72:
69:
68:
52:
49:
48:
43:to compute the
37:Timothy M. Chan
17:
12:
11:
5:
9029:
9019:
9018:
9002:
9001:
8990:(4): 169–174.
8972:
8943:Matoušek, Jiří
8930:
8913:
8906:
8878:
8865:(4): 361–368.
8839:
8838:
8836:
8833:
8832:
8831:
8824:
8821:
8820:
8819:
8807:
8787:
8784:
8781:
8778:
8775:
8772:
8769:
8757:
8756:
8744:
8741:
8738:
8735:
8732:
8729:
8726:
8706:
8703:
8700:
8697:
8694:
8691:
8688:
8677:
8661:
8641:
8621:
8618:
8615:
8612:
8602:lower envelope
8600:Computing the
8593:
8590:
8589:
8588:
8584:
8581:
8573:
8572:Implementation
8570:
8569:
8568:
8567:
8566:
8565:
8564:
8551:
8539:
8526:
8523:
8520:
8498:
8494:
8490:
8485:
8482:
8479:
8475:
8452:
8449:
8446:
8442:
8421:
8404:
8403:
8402:
8401:
8400:
8399:
8398:
8397:
8396:
8395:
8384:
8379:
8376:
8373:
8369:
8365:
8362:
8359:
8356:
8353:
8350:
8335:
8334:
8333:
8322:
8317:
8313:
8309:
8306:
8303:
8298:
8294:
8290:
8285:
8281:
8277:
8274:
8271:
8258:
8243:
8239:
8216:
8213:
8210:
8206:
8193:
8180:
8177:
8174:
8154:
8129:
8125:
8121:
8116:
8113:
8110:
8106:
8092:
8077:
8073:
8050:
8047:
8044:
8040:
8020:
8019:
8018:
8017:
8016:
8015:
8014:
8013:
8002:
7999:
7994:
7991:
7988:
7984:
7980:
7977:
7974:
7969:
7966:
7963:
7959:
7955:
7950:
7947:
7944:
7940:
7936:
7933:
7928:
7924:
7920:
7915:
7912:
7909:
7905:
7901:
7898:
7895:
7892:
7889:
7886:
7883:
7880:
7877:
7874:
7871:
7868:
7865:
7862:
7859:
7856:
7853:
7850:
7847:
7844:
7841:
7838:
7833:
7830:
7827:
7823:
7812:
7799:
7779:
7774:
7770:
7764:
7761:
7758:
7754:
7750:
7730:
7725:
7722:
7719:
7715:
7711:
7708:
7705:
7700:
7697:
7694:
7690:
7686:
7681:
7678:
7675:
7671:
7667:
7664:
7661:
7642:
7641:
7640:
7639:
7638:
7637:
7636:
7635:
7634:
7633:
7622:
7617:
7613:
7609:
7604:
7600:
7596:
7591:
7588:
7585:
7581:
7577:
7574:
7571:
7568:
7565:
7562:
7559:
7556:
7553:
7550:
7547:
7544:
7541:
7538:
7535:
7532:
7529:
7526:
7523:
7520:
7517:
7514:
7509:
7506:
7503:
7499:
7488:
7475:
7463:
7450:
7428:
7424:
7403:
7400:
7397:
7394:
7391:
7388:
7385:
7380:
7376:
7372:
7367:
7364:
7361:
7357:
7336:
7333:
7330:
7318:
7305:
7302:
7299:
7296:
7293:
7288:
7266:
7263:
7260:
7257:
7254:
7251:
7248:
7245:
7242:
7239:
7236:
7233:
7230:
7227:
7224:
7221:
7218:
7215:
7212:
7209:
7197:
7195:can be used .)
7188:
7173:
7170:
7167:
7163:
7142:
7120:
7116:
7111:
7107:
7081:
7075:
7072:
7069:
7065:
7059:
7055:
7031:
7026:
7022:
7016:
7013:
7010:
7006:
7002:
6990:
6988:is maximized ,
6977:
6972:
6968:
6962:
6959:
6956:
6952:
6948:
6926:
6922:
6918:
6915:
6895:
6892:
6889:
6886:
6883:
6880:
6877:
6874:
6871:
6868:
6865:
6862:
6859:
6856:
6853:
6850:
6847:
6844:
6841:
6838:
6812:
6809:
6806:
6803:
6800:
6787:
6774:
6752:
6749:
6746:
6742:
6738:
6735:
6732:
6727:
6724:
6721:
6717:
6713:
6708:
6705:
6702:
6698:
6677:
6665:
6652:
6632:
6612:
6592:
6570:
6567:
6564:
6560:
6556:
6553:
6550:
6545:
6542:
6539:
6535:
6531:
6526:
6523:
6520:
6516:
6503:
6488:
6484:
6463:
6441:
6438:
6435:
6431:
6418:
6403:
6399:
6378:
6366:
6351:
6348:
6345:
6341:
6337:
6334:
6331:
6326:
6323:
6320:
6316:
6312:
6307:
6304:
6301:
6297:
6276:
6256:
6233:
6232:
6231:
6230:
6229:
6228:
6227:
6226:
6211:
6207:
6186:
6167:
6166:
6165:
6164:
6163:
6162:
6148:
6145:
6142:
6139:
6136:
6123:
6110:
6107:
6104:
6101:
6098:
6095:
6090:
6085:
6082:
6077:
6073:
6069:
6066:
6063:
6060:
6055:
6031:
6027:
6023:
6020:
6008:
5996:
5993:
5988:
5984:
5980:
5977:
5972:
5967:
5964:
5957:
5953:
5948:
5944:
5941:
5938:
5935:
5930:
5925:
5922:
5919:
5916:
5913:
5910:
5907:
5902:
5897:
5894:
5891:
5888:
5885:
5881:
5876:
5873:
5868:
5864:
5861:
5856:
5851:
5848:
5845:
5842:
5839:
5836:
5833:
5830:
5825:
5812:
5807:
5794:
5791:
5788:
5785:
5782:
5777:
5763:
5750:
5730:
5727:
5724:
5704:
5684:
5672:
5659:
5637:
5633:
5629:
5626:
5623:
5620:
5608:
5595:
5583:
5570:
5558:
5545:
5529:
5516:
5496:
5476:
5473:
5470:
5467:
5462:
5448:
5435:
5415:
5400:
5396:
5392:
5389:
5386:
5381:
5377:
5373:
5368:
5364:
5341:
5337:
5333:
5330:
5327:
5322:
5318:
5314:
5309:
5305:
5287:
5286:
5285:
5284:
5283:
5282:
5281:
5280:
5269:
5264:
5260:
5256:
5253:
5250:
5247:
5244:
5241:
5238:
5235:
5232:
5229:
5226:
5223:
5220:
5215:
5211:
5200:
5185:
5181:
5158:
5154:
5141:
5128:
5125:
5122:
5119:
5116:
5113:
5108:
5084:
5080:
5059:
5033:
5030:
5027:
5024:
5021:
5008:
4995:
4992:
4989:
4986:
4983:
4980:
4975:
4970:
4967:
4962:
4958:
4954:
4951:
4948:
4945:
4940:
4916:
4912:
4908:
4905:
4893:
4880:
4877:
4874:
4871:
4868:
4865:
4860:
4855:
4852:
4849:
4846:
4843:
4840:
4837:
4834:
4829:
4815:
4800:
4796:
4792:
4789:
4786:
4781:
4777:
4773:
4768:
4764:
4743:
4726:
4725:
4724:
4723:
4722:
4721:
4710:
4707:
4704:
4701:
4698:
4695:
4692:
4689:
4686:
4683:
4680:
4675:
4671:
4667:
4664:
4661:
4656:
4652:
4648:
4643:
4639:
4628:
4615:
4594:
4589:
4586:
4581:
4577:
4574:
4554:
4537:
4536:
4535:
4534:
4533:
4532:
4521:
4516:
4512:
4508:
4505:
4502:
4499:
4496:
4493:
4483:
4472:
4469:
4466:
4463:
4453:
4440:
4423:
4422:
4421:
4420:
4419:
4418:
4403:
4399:
4394:
4390:
4387:
4377:
4364:
4361:
4358:
4353:
4349:
4345:
4342:
4337:
4323:
4309:
4305:
4302:
4299:
4295:
4291:
4288:
4285:
4282:
4279:
4276:
4254:
4250:
4246:
4243:
4231:
4218:
4192:
4189:
4186:
4183:
4180:
4177:
4174:
4171:
4168:
4155:
4140:
4136:
4132:
4127:
4124:
4121:
4117:
4096:
4084:
4071:
4051:
4048:
4045:
4033:
4020:
4008:
3993:
3989:
3968:
3948:
3928:
3916:
3903:
3883:
3880:
3877:
3874:
3871:
3859:
3846:
3843:
3840:
3837:
3834:
3831:
3826:
3812:
3797:
3793:
3789:
3786:
3783:
3780:
3768:
3755:
3735:
3732:
3729:
3717:
3704:
3684:
3672:
3655:
3635:
3620:
3619:
3618:
3617:
3606:
3603:
3600:
3597:
3594:
3591:
3588:
3583:
3579:
3568:
3563:
3550:
3524:
3520:
3507:
3494:
3472:
3468:
3455:
3440:
3436:
3420:
3419:
3418:
3417:
3406:
3403:
3400:
3397:
3394:
3391:
3388:
3385:
3382:
3379:
3376:
3373:
3370:
3367:
3362:
3358:
3347:
3334:
3314:
3311:
3308:
3303:
3289:
3276:
3256:
3241:
3240:
3228:
3208:
3188:
3174:
3162:
3142:
3115:
3095:
3075:
3072:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2990:
2987:
2986:
2985:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2953:
2950:
2946:
2940:
2937:
2934:
2931:
2928:
2925:
2922:
2919:
2916:
2912:
2908:
2905:
2901:
2897:
2894:
2889:
2885:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2856:
2853:
2850:
2846:
2842:
2839:
2836:
2833:
2830:
2826:
2821:
2814:
2810:
2805:
2801:
2797:
2794:
2791:
2787:
2783:
2778:
2775:
2772:
2769:
2766:
2763:
2760:
2755:
2752:
2749:
2745:
2721:
2710:
2709:
2698:
2694:
2691:
2688:
2684:
2681:
2678:
2675:
2671:
2666:
2663:
2660:
2656:
2653:
2650:
2644:
2640:
2635:
2632:
2628:
2624:
2621:
2618:
2615:
2610:
2606:
2601:
2597:
2594:
2591:
2588:
2584:
2577:
2573:
2568:
2564:
2560:
2557:
2553:
2549:
2546:
2539:
2535:
2530:
2526:
2523:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2458:
2450:
2446:
2441:
2437:
2434:
2430:
2426:
2423:
2420:
2400:
2380:
2360:
2344:
2341:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2266:
2246:
2226:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2168:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2116:Jarvis's march
2103:
2083:
2080:
2077:
2057:
2045:
2037:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
1986:
1963:
1943:
1923:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1865:
1862:
1859:
1856:
1853:
1850:
1847:
1844:
1824:
1804:
1784:
1764:
1761:
1758:
1755:
1735:
1732:
1729:
1726:
1706:
1684:
1681:
1678:
1675:
1672:
1668:
1664:
1659:
1655:
1651:
1646:
1642:
1638:
1635:
1632:
1612:
1609:
1606:
1601:
1597:
1593:
1590:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1532:
1512:
1507:
1503:
1499:
1494:
1490:
1486:
1483:
1459:
1456:
1453:
1450:
1447:
1444:
1424:
1419:
1415:
1411:
1406:
1402:
1398:
1395:
1375:
1353:
1349:
1326:
1322:
1301:
1279:
1275:
1252:
1249:
1246:
1242:
1221:
1218:
1215:
1210:
1206:
1202:
1199:
1196:
1191:
1188:
1185:
1181:
1158:
1155:
1152:
1148:
1142:
1138:
1117:
1097:
1094:
1091:
1086:
1082:
1078:
1075:
1072:
1067:
1064:
1061:
1057:
1036:
1016:
994:
990:
967:
963:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
909:
903:
899:
895:
884:Jarvis's march
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
800:
797:
794:
791:
771:
751:
727:
724:
721:
718:
715:
712:
709:
687:
683:
660:
656:
632:
629:
625:
621:
618:
615:
612:
609:
589:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
536:
530:
526:
522:
502:
499:
495:
491:
488:
485:
482:
462:
439:
419:
416:
413:
393:
373:
353:
350:
347:
327:
307:
287:
275:
272:
270:
267:
250:
247:
244:
241:
238:
235:
232:
212:
209:
206:
203:
200:
172:
169:
166:
163:
160:
157:
154:
134:
114:
111:
108:
105:
102:
99:
96:
76:
56:
35:, named after
15:
9:
6:
4:
3:
2:
9028:
9017:
9014:
9013:
9011:
8997:
8993:
8989:
8985:
8984:
8976:
8967:
8962:
8958:
8954:
8953:
8948:
8944:
8940:
8934:
8927:
8923:
8917:
8909:
8903:
8898:
8893:
8889:
8882:
8873:
8868:
8864:
8860:
8859:
8854:
8847:
8845:
8840:
8830:
8827:
8826:
8805:
8782:
8779:
8776:
8773:
8767:
8759:
8758:
8739:
8736:
8733:
8730:
8724:
8701:
8698:
8695:
8692:
8686:
8678:
8675:
8659:
8639:
8616:
8610:
8603:
8599:
8598:
8597:
8585:
8582:
8579:
8578:
8577:
8563:
8549:
8540:
8538:
8524:
8521:
8518:
8496:
8492:
8488:
8483:
8480:
8477:
8473:
8450:
8447:
8444:
8440:
8419:
8410:
8409:
8408:
8407:
8406:
8405:
8377:
8374:
8371:
8367:
8363:
8360:
8354:
8351:
8348:
8341:
8340:
8339:
8336:
8315:
8311:
8307:
8304:
8301:
8296:
8292:
8288:
8283:
8279:
8272:
8269:
8262:
8259:
8257:
8241:
8237:
8214:
8211:
8208:
8204:
8194:
8192:
8178:
8175:
8172:
8152:
8143:
8142:
8127:
8123:
8119:
8114:
8111:
8108:
8104:
8096:
8093:
8091:
8075:
8071:
8048:
8045:
8042:
8038:
8028:
8027:
8026:
8025:
8024:
8023:
8022:
8021:
7992:
7989:
7986:
7982:
7978:
7975:
7972:
7967:
7964:
7961:
7957:
7953:
7948:
7945:
7942:
7938:
7931:
7926:
7922:
7918:
7913:
7910:
7907:
7903:
7896:
7893:
7890:
7887:
7884:
7878:
7875:
7869:
7866:
7863:
7860:
7854:
7851:
7848:
7845:
7842:
7839:
7836:
7831:
7828:
7825:
7821:
7813:
7811:
7797:
7777:
7772:
7768:
7762:
7759:
7756:
7752:
7748:
7723:
7720:
7717:
7713:
7709:
7706:
7703:
7698:
7695:
7692:
7688:
7684:
7679:
7676:
7673:
7669:
7662:
7659:
7650:
7649:
7648:
7647:
7646:
7645:
7644:
7643:
7615:
7611:
7607:
7602:
7598:
7594:
7589:
7586:
7583:
7579:
7572:
7569:
7566:
7563:
7560:
7557:
7551:
7548:
7545:
7542:
7539:
7536:
7530:
7527:
7524:
7521:
7518:
7515:
7512:
7507:
7504:
7501:
7497:
7489:
7487:
7473:
7464:
7462:
7448:
7426:
7422:
7398:
7395:
7389:
7383:
7378:
7374:
7370:
7365:
7362:
7359:
7355:
7334:
7331:
7328:
7319:
7317:
7300:
7297:
7294:
7264:
7261:
7258:
7255:
7252:
7249:
7243:
7240:
7237:
7234:
7231:
7228:
7222:
7219:
7216:
7213:
7210:
7207:
7198:
7196:
7194:
7189:
7187:
7171:
7168:
7165:
7161:
7153:is stored in
7140:
7118:
7114:
7109:
7105:
7079:
7073:
7070:
7067:
7063:
7057:
7053:
7029:
7024:
7020:
7014:
7011:
7008:
7004:
7000:
6991:
6989:
6975:
6970:
6966:
6960:
6957:
6954:
6950:
6946:
6924:
6920:
6916:
6913:
6893:
6890:
6887:
6884:
6881:
6878:
6872:
6869:
6866:
6863:
6860:
6857:
6851:
6848:
6845:
6842:
6839:
6836:
6827:
6826:
6825:
6810:
6807:
6804:
6801:
6798:
6791:
6788:
6786:
6772:
6750:
6747:
6744:
6740:
6736:
6733:
6730:
6725:
6722:
6719:
6715:
6711:
6706:
6703:
6700:
6696:
6675:
6666:
6664:
6650:
6630:
6610:
6590:
6568:
6565:
6562:
6558:
6554:
6551:
6548:
6543:
6540:
6537:
6533:
6529:
6524:
6521:
6518:
6514:
6504:
6502:
6486:
6482:
6461:
6439:
6436:
6433:
6429:
6419:
6417:
6401:
6397:
6376:
6367:
6365:
6349:
6346:
6343:
6339:
6335:
6332:
6329:
6324:
6321:
6318:
6314:
6310:
6305:
6302:
6299:
6295:
6274:
6254:
6246:
6241:
6240:
6239:
6238:
6237:
6236:
6235:
6234:
6225:
6209:
6205:
6184:
6175:
6174:
6173:
6172:
6171:
6170:
6169:
6168:
6161:
6146:
6143:
6140:
6137:
6134:
6127:
6124:
6122:
6105:
6102:
6099:
6096:
6083:
6075:
6071:
6067:
6064:
6061:
6029:
6025:
6021:
6018:
6009:
6007:
5994:
5986:
5982:
5978:
5965:
5955:
5951:
5946:
5942:
5939:
5936:
5923:
5917:
5914:
5911:
5908:
5895:
5889:
5886:
5883:
5879:
5874:
5871:
5866:
5862:
5849:
5843:
5840:
5837:
5834:
5831:
5813:
5811:
5808:
5806:
5789:
5786:
5783:
5764:
5762:
5748:
5728:
5725:
5722:
5702:
5682:
5673:
5671:
5657:
5635:
5631:
5627:
5624:
5621:
5618:
5609:
5607:
5593:
5584:
5582:
5568:
5559:
5557:
5543:
5535:
5530:
5528:
5514:
5494:
5471:
5468:
5449:
5447:
5433:
5425:
5421:
5416:
5414:
5398:
5394:
5390:
5387:
5384:
5379:
5375:
5371:
5366:
5362:
5339:
5335:
5331:
5328:
5325:
5320:
5316:
5312:
5307:
5303:
5293:
5292:
5291:
5290:
5289:
5288:
5262:
5258:
5251:
5248:
5245:
5242:
5236:
5233:
5230:
5227:
5224:
5221:
5218:
5213:
5209:
5201:
5199:
5183:
5179:
5156:
5152:
5142:
5140:
5123:
5120:
5117:
5114:
5082:
5078:
5057:
5048:
5047:
5046:
5031:
5028:
5025:
5022:
5019:
5012:
5009:
5007:
4990:
4987:
4984:
4981:
4968:
4960:
4956:
4952:
4949:
4946:
4914:
4910:
4906:
4903:
4894:
4892:
4875:
4872:
4869:
4866:
4853:
4847:
4844:
4841:
4838:
4835:
4816:
4814:
4798:
4794:
4790:
4787:
4784:
4779:
4775:
4771:
4766:
4762:
4741:
4732:
4731:
4730:
4729:
4728:
4727:
4705:
4702:
4699:
4693:
4690:
4687:
4684:
4681:
4678:
4673:
4669:
4665:
4662:
4659:
4654:
4650:
4646:
4641:
4637:
4629:
4627:
4613:
4592:
4587:
4584:
4579:
4575:
4572:
4552:
4543:
4542:
4541:
4540:
4539:
4538:
4514:
4510:
4506:
4503:
4497:
4494:
4491:
4484:
4464:
4461:
4454:
4452:
4438:
4429:
4428:
4427:
4426:
4425:
4424:
4401:
4397:
4392:
4388:
4385:
4378:
4376:
4359:
4356:
4351:
4347:
4343:
4324:
4322:
4307:
4303:
4300:
4297:
4293:
4289:
4286:
4283:
4280:
4277:
4274:
4252:
4248:
4244:
4241:
4232:
4230:
4216:
4207:
4206:
4205:
4190:
4187:
4184:
4181:
4178:
4175:
4172:
4169:
4166:
4159:
4156:
4154:
4138:
4134:
4130:
4125:
4122:
4119:
4115:
4094:
4085:
4083:
4069:
4049:
4046:
4043:
4034:
4032:
4018:
4009:
4007:
3991:
3987:
3966:
3946:
3926:
3917:
3915:
3901:
3881:
3878:
3875:
3872:
3869:
3860:
3858:
3841:
3838:
3835:
3832:
3813:
3811:
3795:
3791:
3787:
3784:
3781:
3778:
3769:
3767:
3753:
3733:
3730:
3727:
3718:
3716:
3702:
3682:
3673:
3671:
3669:
3653:
3633:
3624:
3623:
3622:
3621:
3601:
3598:
3592:
3586:
3581:
3577:
3569:
3567:
3564:
3562:
3548:
3540:
3522:
3518:
3508:
3506:
3492:
3470:
3466:
3456:
3454:
3438:
3434:
3424:
3423:
3422:
3421:
3401:
3395:
3392:
3389:
3386:
3383:
3377:
3374:
3371:
3368:
3365:
3360:
3356:
3348:
3346:
3332:
3309:
3290:
3288:
3274:
3254:
3245:
3244:
3243:
3242:
3226:
3206:
3186:
3178:
3175:
3160:
3140:
3132:
3129:
3128:
3127:
3113:
3093:
3085:
3081:
3071:
3054:
3051:
3048:
3045:
3039:
3015:
3012:
3009:
3006:
3000:
2972:
2966:
2963:
2960:
2957:
2951:
2948:
2944:
2935:
2932:
2929:
2926:
2923:
2917:
2914:
2910:
2906:
2903:
2899:
2895:
2892:
2887:
2883:
2874:
2871:
2868:
2865:
2862:
2854:
2851:
2848:
2844:
2837:
2831:
2828:
2824:
2819:
2812:
2808:
2803:
2799:
2795:
2792:
2789:
2785:
2781:
2773:
2770:
2767:
2764:
2761:
2753:
2750:
2747:
2743:
2735:
2734:
2733:
2719:
2696:
2692:
2689:
2686:
2682:
2679:
2676:
2673:
2664:
2661:
2658:
2654:
2651:
2648:
2642:
2638:
2633:
2630:
2622:
2619:
2616:
2613:
2608:
2604:
2595:
2592:
2589:
2586:
2582:
2575:
2571:
2566:
2562:
2558:
2555:
2547:
2544:
2537:
2533:
2528:
2524:
2521:
2514:
2513:
2512:
2495:
2492:
2489:
2486:
2483:
2477:
2456:
2448:
2444:
2439:
2435:
2432:
2428:
2421:
2418:
2398:
2378:
2358:
2351:the value of
2350:
2340:
2323:
2320:
2317:
2314:
2308:
2305:
2299:
2296:
2293:
2290:
2284:
2264:
2244:
2224:
2201:
2198:
2195:
2192:
2186:
2166:
2157:
2140:
2137:
2134:
2131:
2125:
2117:
2101:
2081:
2078:
2075:
2055:
2043:
2036:
2019:
2016:
2013:
2010:
2004:
1984:
1975:
1961:
1941:
1921:
1898:
1895:
1892:
1889:
1883:
1860:
1857:
1854:
1851:
1848:
1842:
1822:
1802:
1782:
1759:
1753:
1730:
1724:
1704:
1682:
1679:
1676:
1673:
1670:
1657:
1653:
1649:
1644:
1640:
1633:
1607:
1604:
1599:
1595:
1588:
1565:
1562:
1559:
1556:
1550:
1530:
1505:
1501:
1497:
1492:
1488:
1481:
1473:
1472:binary search
1454:
1451:
1448:
1442:
1417:
1413:
1409:
1404:
1400:
1393:
1373:
1351:
1347:
1324:
1320:
1299:
1277:
1273:
1250:
1247:
1244:
1240:
1216:
1213:
1208:
1204:
1197:
1194:
1189:
1186:
1183:
1179:
1156:
1153:
1150:
1146:
1140:
1136:
1115:
1092:
1089:
1084:
1080:
1073:
1070:
1065:
1062:
1059:
1055:
1034:
1014:
992:
988:
965:
961:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
901:
897:
885:
880:
863:
860:
857:
854:
848:
845:
839:
836:
833:
830:
824:
821:
818:
795:
789:
769:
749:
741:
722:
719:
716:
713:
707:
685:
681:
658:
654:
644:
627:
623:
619:
613:
610:
607:
587:
580:with at most
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
528:
524:
497:
493:
489:
483:
480:
460:
451:
437:
417:
414:
411:
391:
371:
351:
348:
345:
325:
305:
285:
266:
264:
245:
242:
239:
236:
230:
207:
204:
198:
190:
186:
167:
164:
161:
158:
152:
132:
109:
106:
103:
100:
94:
74:
54:
46:
42:
38:
34:
30:
21:
8987:
8981:
8975:
8956:
8950:
8933:
8916:
8887:
8881:
8862:
8856:
8595:
8575:
8541:
8411:
8337:
8260:
8195:
8144:
8094:
8029:
7651:
7465:
7320:
7199:
7190:
6992:
6828:
6823:
6789:
6667:
6623:, there are
6505:
6420:
6368:
6244:
6242:
6176:
6159:
6125:
6010:
5814:
5809:
5765:
5674:
5610:
5585:
5560:
5531:
5487:time, where
5450:
5424:Jarvis march
5423:
5419:
5418:(Now, use a
5417:
5294:
5143:
5049:
5044:
5010:
4895:
4817:
4733:
4544:
4430:
4325:
4233:
4208:
4203:
4157:
4086:
4035:
4010:
3918:
3861:
3814:
3770:
3719:
3674:
3667:
3625:
3565:
3538:
3509:
3457:
3425:
3291:
3246:
3176:
3130:
3084:Jarvis march
3077:
2992:
2711:
2348:
2346:
2158:
2047:
2041:
1976:
1934:is close to
1523:for all the
881:
645:
452:
338:). Ideally,
277:
189:Jarvis march
125:time, where
32:
26:
3541:a point of
3080:Graham scan
782:subsets of
740:Graham scan
700:, using an
185:Graham scan
183:algorithm (
45:convex hull
8835:References
8592:Extensions
8587:increased.
8412:(If after
6583:depend on
4818:(It takes
3074:Pseudocode
8959:: 27–32.
8780:
8737:
8699:
8674:trapezoid
8632:of a set
8305:…
7976:…
7911:−
7882:_
7873:_
7858:_
7760:−
7749:∡
7707:…
7663:∈
7587:−
7555:_
7534:_
7393:∞
7390:−
7363:−
7298:
7247:_
7226:_
7119:→
7080:→
7071:−
7012:−
7001:∡
6958:−
6947:∡
6917:∈
6876:_
6855:_
6808:≤
6802:≤
6734:…
6552:…
6421:that is,
6333:…
6144:≤
6138:≤
6103:
6068:
6022:≤
5943:
5915:
5887:
5841:
5787:
5628:≤
5622:≤
5611:(We want
5388:…
5329:…
5240:_
5121:
5029:≤
5023:≤
4988:
4953:
4907:≤
4873:
4845:
4788:…
4663:…
4357:
4301:
4287:…
4188:
4182:
4176:≤
4170:≤
4047:≠
3879:
3873:
3839:
3788:≤
3782:≤
3731:≤
3596:∞
3593:−
3381:_
3052:
3013:
2964:
2939:⌉
2933:
2927:
2921:⌈
2907:⋅
2878:⌉
2872:
2866:
2860:⌈
2845:∑
2796:
2777:⌉
2771:
2765:
2759:⌈
2744:∑
2690:
2683:
2677:≥
2670:⟺
2662:
2655:
2649:≥
2634:
2627:⟺
2620:
2614:≥
2600:⟺
2593:
2587:≥
2559:
2552:⟺
2545:≥
2493:
2487:
2321:
2297:
2217:time. If
2199:
2138:
2017:
1896:
1858:
1680:≤
1674:≤
1563:
1452:
861:
837:
822:⋅
742:), where
720:
501:⌉
487:⌈
415:≥
269:Algorithm
243:
165:
107:
47:of a set
9010:Category
8945:(1995).
8823:See also
8191:points.)
5880:⌉
5867:⌈
4593:⌉
4580:⌈
4308:⌉
4294:⌈
3173:points .
1914:time if
1470:time by
513:subsets
274:Overview
8928:, 1996.
8511:, then
7133:. Such
6506:(Note:
5715:, i.e.
5422:of the
3670:known.)
3626:(Note:
3510:(Note:
3177:Output:
8904:
8261:return
7316:time.)
6993:where
6247:loop,
5139:time.)
4891:time.)
4267:, for
3131:Input:
2349:square
2035:time.
879:time.
8926:INRIA
5805:time.
4565:into
3666:, is
3199:with
3153:with
473:into
8902:ISBN
8522:<
8338:else
7414:and
7094:and
5726:<
3179:Set
3133:Set
3082:and
2306:>
2079:<
1292:and
364:but
8992:doi
8961:doi
8892:doi
8867:doi
8777:log
8734:log
8696:log
8652:of
7295:log
6790:for
6245:for
6126:for
6100:log
6065:log
6011:If
5940:log
5912:log
5884:log
5838:log
5784:log
5118:log
5011:for
4985:log
4950:log
4896:If
4870:log
4842:log
4348:log
4298:log
4185:log
4179:log
4158:for
3876:log
3870:log
3836:log
3668:not
3539:not
3537:is
3049:log
3010:log
2961:log
2930:log
2924:log
2869:log
2863:log
2793:log
2768:log
2762:log
2687:log
2680:log
2659:log
2652:log
2631:log
2617:log
2590:log
2556:log
2490:log
2484:log
2425:min
2318:log
2294:log
2196:log
2135:log
2014:log
1893:log
1855:log
1560:log
1449:log
1435:in
858:log
834:log
717:log
450:).
240:log
162:log
104:log
67:of
27:In
9012::
8988:33
8986:.
8955:.
8949:.
8941:;
8900:.
8863:16
8861:.
8855:.
8843:^
8562:.)
8537:.)
8489:==
8273::=
8256:.)
8120:==
8095:if
8090:.)
7837::=
7810:.)
7513::=
7347:,
7186:.)
6824:do
6785:.)
6663:.)
6501:.)
6287:,
6224:.)
6160:do
6121:.)
5556:.)
5446:.)
5219::=
5198:.)
5070:,
5045:do
5006:.)
4813:.)
4679::=
4465::=
4389::=
4375:.)
4204:do
4153:.)
4131:==
4006:.)
3914:.)
3857:.)
3766:.)
3715:.)
3587::=
3561:.)
3505:.)
3366::=
3345:.)
3126:.
3070:.
2411:,
2339:.
1339:,
643:.
31:,
8998:.
8994::
8969:.
8963::
8957:5
8910:.
8894::
8875:.
8869::
8818:.
8806:n
8786:)
8783:h
8774:n
8771:(
8768:O
8743:)
8740:h
8731:n
8728:(
8725:O
8705:)
8702:n
8693:n
8690:(
8687:O
8660:n
8640:S
8620:)
8617:S
8614:(
8611:L
8550:m
8525:h
8519:m
8497:1
8493:p
8484:1
8481:+
8478:i
8474:p
8451:1
8448:+
8445:i
8441:p
8420:m
8383:)
8378:1
8375:+
8372:i
8368:p
8364:,
8361:C
8358:(
8355:D
8352:D
8349:A
8321:)
8316:i
8312:p
8308:,
8302:,
8297:2
8293:p
8289:,
8284:1
8280:p
8276:(
8270:C
8242:1
8238:p
8215:1
8212:+
8209:i
8205:p
8179:h
8176:=
8173:i
8153:P
8128:1
8124:p
8115:1
8112:+
8109:i
8105:p
8076:1
8072:p
8049:1
8046:+
8043:i
8039:p
8001:)
7998:)
7993:K
7990:,
7987:i
7983:q
7979:,
7973:,
7968:2
7965:,
7962:i
7958:q
7954:,
7949:1
7946:,
7943:i
7939:q
7935:(
7932:,
7927:i
7923:p
7919:,
7914:1
7908:i
7904:p
7900:(
7897:T
7894:N
7891:I
7888:O
7885:P
7879:H
7876:C
7870:T
7867:X
7864:E
7861:N
7855:S
7852:I
7849:V
7846:R
7843:A
7840:J
7832:1
7829:+
7826:i
7822:p
7798:P
7778:z
7773:i
7769:p
7763:1
7757:i
7753:p
7729:}
7724:K
7721:,
7718:i
7714:q
7710:,
7704:,
7699:2
7696:,
7693:i
7689:q
7685:,
7680:1
7677:,
7674:i
7670:q
7666:{
7660:z
7621:)
7616:k
7612:C
7608:,
7603:i
7599:p
7595:,
7590:1
7584:i
7580:p
7576:(
7573:H
7570:C
7567:R
7564:A
7561:E
7558:S
7552:Y
7549:R
7546:A
7543:N
7540:I
7537:B
7531:S
7528:I
7525:V
7522:R
7519:A
7516:J
7508:k
7505:,
7502:i
7498:q
7474:P
7461::
7449:P
7427:1
7423:p
7402:)
7399:0
7396:,
7387:(
7384:=
7379:0
7375:p
7371:=
7366:1
7360:i
7356:p
7335:1
7332:=
7329:i
7304:)
7301:m
7292:(
7287:O
7265:H
7262:C
7259:R
7256:A
7253:E
7250:S
7244:Y
7241:R
7238:A
7235:N
7232:I
7229:B
7223:S
7220:I
7217:V
7214:R
7211:A
7208:J
7200:(
7172:k
7169:,
7166:i
7162:q
7141:d
7115:d
7110:i
7106:p
7074:1
7068:i
7064:p
7058:i
7054:p
7030:d
7025:i
7021:p
7015:1
7009:i
7005:p
6976:d
6971:i
6967:p
6961:1
6955:i
6951:p
6925:k
6921:C
6914:d
6894:H
6891:C
6888:R
6885:A
6882:E
6879:S
6873:Y
6870:R
6867:A
6864:N
6861:I
6858:B
6852:S
6849:I
6846:V
6843:R
6840:A
6837:J
6829:(
6811:K
6805:k
6799:1
6773:P
6751:K
6748:,
6745:i
6741:q
6737:,
6731:,
6726:2
6723:,
6720:i
6716:q
6712:,
6707:1
6704:,
6701:i
6697:q
6676:i
6651:P
6631:K
6611:i
6591:i
6569:K
6566:,
6563:i
6559:q
6555:,
6549:,
6544:2
6541:,
6538:i
6534:q
6530:,
6525:1
6522:,
6519:i
6515:q
6487:k
6483:C
6462:P
6440:k
6437:,
6434:i
6430:q
6416::
6402:k
6398:C
6377:K
6350:K
6347:,
6344:i
6340:q
6336:,
6330:,
6325:2
6322:,
6319:i
6315:q
6311:,
6306:1
6303:,
6300:i
6296:q
6275:P
6255:K
6210:1
6206:p
6185:P
6147:m
6141:i
6135:1
6109:)
6106:h
6097:n
6094:(
6089:O
6084:=
6081:)
6076:2
6072:h
6062:n
6059:(
6054:O
6030:2
6026:h
6019:m
5995:.
5992:)
5987:t
5983:2
5979:n
5976:(
5971:O
5966:=
5963:)
5956:t
5952:2
5947:2
5937:n
5934:(
5929:O
5924:=
5921:)
5918:m
5909:n
5906:(
5901:O
5896:=
5893:)
5890:m
5875:m
5872:n
5863:m
5860:(
5855:O
5850:=
5847:)
5844:m
5835:K
5832:m
5829:(
5824:O
5793:)
5790:m
5781:(
5776:O
5749:P
5729:h
5723:m
5703:h
5683:m
5658:m
5636:2
5632:h
5625:m
5619:h
5594:n
5569:h
5544:h
5515:h
5495:n
5475:)
5472:h
5469:n
5466:(
5461:O
5434:P
5399:K
5395:Q
5391:,
5385:,
5380:2
5376:Q
5372:,
5367:1
5363:Q
5340:K
5336:C
5332:,
5326:,
5321:2
5317:C
5313:,
5308:1
5304:C
5268:)
5263:k
5259:Q
5255:(
5252:N
5249:A
5246:C
5243:S
5237:M
5234:A
5231:H
5228:A
5225:R
5222:G
5214:k
5210:C
5184:k
5180:Q
5157:k
5153:C
5144:(
5127:)
5124:m
5115:m
5112:(
5107:O
5083:k
5079:Q
5058:k
5032:K
5026:k
5020:1
4994:)
4991:h
4982:n
4979:(
4974:O
4969:=
4966:)
4961:2
4957:h
4947:n
4944:(
4939:O
4915:2
4911:h
4904:m
4879:)
4876:m
4867:n
4864:(
4859:O
4854:=
4851:)
4848:m
4839:m
4836:K
4833:(
4828:O
4799:K
4795:Q
4791:,
4785:,
4780:2
4776:Q
4772:,
4767:1
4763:Q
4742:K
4709:)
4706:m
4703:,
4700:P
4697:(
4694:T
4691:I
4688:L
4685:P
4682:S
4674:K
4670:Q
4666:,
4660:,
4655:2
4651:Q
4647:,
4642:1
4638:Q
4614:m
4588:m
4585:n
4576:=
4573:K
4553:P
4520:)
4515:1
4511:p
4507:,
4504:C
4501:(
4498:D
4495:D
4492:A
4471:)
4468:(
4462:C
4439:P
4402:t
4398:2
4393:2
4386:m
4363:)
4360:h
4352:2
4344:n
4341:(
4336:O
4321:.
4304:h
4290:,
4284:,
4281:1
4278:=
4275:t
4253:t
4249:2
4245:=
4242:m
4217:m
4191:n
4173:t
4167:1
4139:1
4135:p
4126:1
4123:+
4120:i
4116:p
4095:C
4070:m
4050:h
4044:m
4019:h
3992:2
3988:h
3967:h
3947:h
3927:m
3902:m
3882:n
3845:)
3842:h
3833:n
3830:(
3825:O
3796:2
3792:h
3785:m
3779:h
3754:P
3734:m
3728:h
3720:(
3703:h
3683:m
3654:P
3634:h
3605:)
3602:0
3599:,
3590:(
3582:0
3578:p
3549:P
3523:0
3519:p
3493:P
3471:2
3467:p
3439:0
3435:p
3426:(
3405:)
3402:P
3399:(
3396:T
3393:R
3390:A
3387:T
3384:S
3378:K
3375:C
3372:I
3369:P
3361:1
3357:p
3333:P
3313:)
3310:n
3307:(
3302:O
3275:C
3255:P
3239:.
3227:P
3207:h
3187:C
3161:n
3141:P
3114:P
3094:C
3058:)
3055:h
3046:n
3043:(
3040:O
3019:)
3016:n
3007:n
3004:(
3001:O
2973:.
2970:)
2967:h
2958:n
2955:(
2952:O
2949:=
2945:)
2936:h
2918:+
2915:1
2911:2
2904:n
2900:(
2896:O
2893:=
2888:t
2884:2
2875:h
2855:0
2852:=
2849:t
2841:)
2838:n
2835:(
2832:O
2829:=
2825:)
2820:)
2813:t
2809:2
2804:2
2800:(
2790:n
2786:(
2782:O
2774:h
2754:0
2751:=
2748:t
2720:2
2697:,
2693:h
2674:t
2665:h
2643:t
2639:2
2623:h
2609:t
2605:2
2596:h
2583:)
2576:t
2572:2
2567:2
2563:(
2548:h
2538:t
2534:2
2529:2
2525:=
2522:m
2499:)
2496:h
2481:(
2478:O
2457:)
2449:t
2445:2
2440:2
2436:,
2433:n
2429:(
2422:=
2419:m
2399:t
2379:n
2359:m
2327:)
2324:h
2315:n
2312:(
2309:O
2303:)
2300:m
2291:n
2288:(
2285:O
2265:h
2245:m
2225:m
2205:)
2202:m
2193:n
2190:(
2187:O
2167:m
2144:)
2141:m
2132:n
2129:(
2126:O
2102:m
2082:h
2076:m
2056:m
2042:m
2023:)
2020:h
2011:n
2008:(
2005:O
1985:n
1962:m
1942:h
1922:m
1902:)
1899:h
1890:n
1887:(
1884:O
1864:)
1861:m
1852:h
1849:K
1846:(
1843:O
1823:P
1803:h
1783:h
1763:)
1760:h
1757:(
1754:O
1734:)
1731:K
1728:(
1725:O
1705:P
1683:K
1677:k
1671:1
1667:)
1663:)
1658:k
1654:Q
1650:,
1645:i
1641:p
1637:(
1634:f
1631:(
1611:)
1608:P
1605:,
1600:i
1596:p
1592:(
1589:f
1569:)
1566:m
1557:K
1554:(
1551:O
1531:K
1511:)
1506:k
1502:Q
1498:,
1493:i
1489:p
1485:(
1482:f
1458:)
1455:m
1446:(
1443:O
1423:)
1418:k
1414:Q
1410:,
1405:i
1401:p
1397:(
1394:f
1374:m
1352:k
1348:C
1325:k
1321:Q
1300:P
1278:i
1274:p
1251:1
1248:+
1245:i
1241:p
1220:)
1217:P
1214:,
1209:i
1205:p
1201:(
1198:f
1195:=
1190:1
1187:+
1184:i
1180:p
1157:1
1154:+
1151:i
1147:p
1141:i
1137:p
1116:P
1096:)
1093:P
1090:,
1085:i
1081:p
1077:(
1074:f
1071:=
1066:1
1063:+
1060:i
1056:p
1035:P
1015:P
993:i
989:p
966:i
962:p
939:K
936:.
933:.
930:.
927:,
924:2
921:,
918:1
915:=
912:k
908:)
902:k
898:C
894:(
867:)
864:m
855:n
852:(
849:O
846:=
843:)
840:m
831:m
828:(
825:O
819:K
799:)
796:m
793:(
790:O
770:K
750:p
726:)
723:p
714:p
711:(
708:O
686:k
682:C
659:k
655:Q
631:)
628:m
624:/
620:n
617:(
614:O
611:=
608:K
588:m
566:K
563:.
560:.
557:.
554:,
551:2
548:,
545:1
542:=
539:k
535:)
529:k
525:Q
521:(
498:m
494:/
490:n
484:=
481:K
461:P
438:m
418:h
412:m
392:m
372:h
352:h
349:=
346:m
326:P
306:n
286:m
249:)
246:h
237:n
234:(
231:O
211:)
208:h
205:n
202:(
199:O
191:(
171:)
168:n
159:n
156:(
153:O
133:h
113:)
110:h
101:n
98:(
95:O
75:n
55:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
