1376:
processors synchronized with each other: instead, one can allow some of them to progress farther through the sorting algorithm while others wait for the results of their comparisons to be determined. Based on this principle, Cole modifies the simulation of the sorting algorithm, so that it maintains a collection of unresolved simulated comparisons that may not all come from the same parallel time step of the test algorithm. As in the synchronized parallel version of parametric search, it is possible to resolve half of these comparisons by finding the median comparison value and calling the decision algorithm on this value. Then, instead of repeating this halving procedure until the collection of unresolved comparisons becomes empty, Cole allows the processors that were waiting on the resolved comparisons to advance through the simulation until they reach another comparison that must be resolved. Using this method, Cole shows that a parametric search algorithm in which the test algorithm is sorting may be completed using only a logarithmic number of calls to the decision algorithm, instead of the
1482:
which the number of unresolved comparisons is halved by finding the median comparison value and calling the decision algorithm with that value. As they show, the resulting randomized parametric search algorithm makes only a logarithmic number of calls to the decision algorithm with high probability, matching Cole's theoretical analysis. An extended version of their paper includes experimental results from an implementation of the algorithm, which show that the total running time of this method on several natural geometric optimization problems is similar to that of the best synchronized parametric search implementation (the quicksort-based method of van
Oostrum and Veltkamp): a little faster on some problems and a little slower on some others. However, the number of calls that it makes to the decision algorithm is significantly smaller, so this method would obtain greater benefits in applications of parametric searching where the decision algorithm is slower.
1573:
1364:
the simulated test algorithm are sufficiently evenly distributed, then as the algorithm progresses the number of unresolved comparisons generated in each time step will be small. Based on this heuristic analysis, and on experimental results with an implementation of the algorithm, they argue that a quicksort-based parametric search algorithm will be more practical than its worst-case analysis would suggest.
812:– can be performed by running the same decision algorithm with the crossing time for the particle as its parameter. Thus, the simulation ends up running the decision algorithm on each of the particle crossing times, one of which must be the optimal crossing time. Running the decision algorithm once takes linear time, so running it separately on each crossing time takes quadratic time.
456:, and uses the result of the decision algorithm to determine the output of the comparison. In this way, the time for the simulation ends up equalling the product of the times for the test and decision algorithms. Because the test algorithm is assumed to behave discontinuously at the optimal solution value, it cannot be simulated accurately unless one of the parameter values
1359:(an algorithm that repeatedly partitions the input into two subsets and then recursively sorts each subset). In this algorithm, the partition step is massively parallel (each input element should be compared to a chosen pivot element) and the two recursive calls can be performed in parallel with each other. The resulting parametric algorithm is slower in the
355:
In the most basic form of the parametric search technique, both the test algorithm and the decision algorithms are sequential (non-parallel) algorithms, possibly the same algorithm as each other. The technique simulates the test algorithm step by step, as it would run when given the (unknown) optimal
1481:
smaller subproblems instead of only two subproblems. As in Cole's technique, they use a desynchronized parametric search, in which each separate thread of execution of the simulated parallel sorting algorithm is allowed to progress until it needs to determine the result of another comparison, and in
1363:
than an algorithm based on the AKS sorting network. However, van
Oostrum and Veltkamp argue that if the results of past decision algorithms are saved (so that only the comparisons unresolved by these results will lead to additional calls to the decision algorithm) and the comparison values tested by
1133:
algorithm that sorts the positions of the particles at the time given by the algorithm's parameter, and then uses the sorted order to determine the median particle and find the sign of its position. The best choice for this algorithm (according to its theoretical analysis, if not in practice) is the
815:
Megiddo remarks that, for this specific problem, there exists a simple linear time algorithm that does not involve parametric search: just determine the time at which each particle crosses the origin and return the median of these times. However, he explains that parametric search often matches the
512:
concerns a system of an odd number of particles, all moving rightward at different constant speeds along the same line. The median of the particles, also, will have a rightward motion, but one that is piecewise linear rather than having constant speed, because different particles will be the median
1375:
further optimized the parametric search technique for cases (such as the example) in which the test algorithm is a comparison sorting algorithm. For the AKS sorting network and some other sorting algorithms that can be used in its place, Cole observes that it is not necessary to keep the simulated
1547:
Instead, when applicable, parametric search finds strongly polynomial algorithms, whose running time is a function only of the input size and is independent of numerical precision. However, parametric search leads to an increase in time complexity (compared to the decision algorithm) that may be
920:
numerical comparisons. By finding a median or near-median value in the set of comparisons that need to be evaluated, and passing this single value to the decision algorithm, it is possible to eliminate half or nearly half of the comparisons with only a single call of the decision algorithm. By
1539:
of numbers, known to contain the optimal solution value, and repeatedly shrinks the interval by calling the decision algorithm on its median value and keeping only the half-interval above or below the median, depending on the outcome of the call. Although this method can only find a numerical
1347:
total time for the parametric search. This is not the optimal time for this problem – the same problem can be solved more quickly by observing that the crossing time of the median equals the median of the crossing times of the particles – but the same technique can be applied to other more
1803:
problem (determining the first object in a scene that is intersected by a given line of sight or light beam) can be solved by combining parametric search with a data structure for a simpler problem, testing whether any of a given set of obstacles occludes a given ray
476:
passed to the decision algorithm is actually equal to the optimal solution value. When this happens, the decision algorithm can detect the equality and save the optimal solution value for later output. If the test algorithm needs to know the sign of a polynomial in
1548:
larger than logarithmic. Because they are strongly rather than weakly polynomial, algorithms based on parametric search are more satisfactory from a theoretical point of view. In practice, binary search is fast and often much simpler to implement, so
1426:, resulting in time bounds with smaller constant factors that, however, are still not small enough to be practical. A similar speedup can be obtained for any problem that can be computed on a distributed computing network of bounded
1556:
write that "while a simple binary-search approach is often advocated as a practical replacement for parametric search, it is outperformed by our algorithm" in the experimental comparisons that they performed.
1101:
calls per batch). Often, for a problem that can be solved in this way, the time-processor product of the PRAM algorithm is comparable to the time for a sequential decision algorithm, and the parallel time is
1540:
approximation to the optimal solution value, it does so in a number of calls to the decision algorithm proportional to the number of bits of precision of accuracy for this approximation, resulting in
2320:. Parametric search can also be used for other similar problems of finding the time at which some measure of a set of moving points obtains its minimum value, for measures including the size of the
2103:
1675:
using other algorithmic techniques. However, this improvement does not extend to higher dimensions. In three dimensions, parametric search can be used to find centerpoints in time
1978:
1867:
1725:
1351:
Because of the large constant factors arising in the analysis of the AKS sorting network, parametric search using this network as the test algorithm is not practical. Instead,
347:
as the test algorithm, and group the comparisons that must be simulated into batches, in order to significantly reduce the number of instantiations of the decision algorithm.
2318:
2024:
1913:
1479:
1345:
1416:
2202:
1770:
1521:
1230:
1044:
652:
619:
1300:
1265:
1099:
974:
900:
steps in which each processor performs a single operation), then each of its steps may be simulated by using the decision algorithm to determine the results of at most
1564:) can be used in place of parametric search. This method only incurs a constant factor increase in time complexity while still giving a strongly polynomial algorithm.
1418:
calls made by
Megiddo's original version of parametric search. Instead of using the AKS sorting network, it is also possible to combine this technique with a parallel
1669:
152:
1006:
810:
783:
756:
729:
702:
542:
337:
307:
115:
2269:
2242:
2222:
2143:
2123:
1998:
1887:
1629:
1192:
1172:
1127:
1064:
939:
918:
898:
878:
858:
672:
586:
566:
495:
474:
454:
434:
414:
394:
374:
280:
260:
236:
216:
192:
172:
88:
677:
Using this decision algorithm as both the test algorithm and the decision algorithm of a parametric search leads to an algorithm for finding the optimal time
1485:
On the example problem of finding the median crossing time of a point, both Cole's algorithm and the algorithm of
Goodrich and Pszona obtain running time
501:
to the decision algorithm in order to determine whether the unknown solution value is one of these roots, or, if not, which two roots it lies between.
921:
repeatedly halving the set of comparisons required by the simulation in this way, until none are left, it is possible to simulate the results of
1926:
that contains a given point set and has the smallest possible width (difference between inner and outer radii) can be used as a measure of the
2347:
828:
already observed, the parametric search technique can be substantially sped up by replacing the simulated test algorithm by an efficient
2885:
2831:
785:. Answering this question for a single particle – comparing the crossing time for the particle with the unknown optimal crossing time
2438:
1143:
2858:
2555:
2479:
1348:
complicated optimization problems, and in many cases provides the fastest known strongly polynomial algorithm for these problems.
2462:
1106:, leading to a total time for the parametric search that is slower than the decision algorithm by only a polylogarithmic factor.
1444:. Instead of using a parallel quicksort, as van Oostrum and Veltkamp did, they use boxsort, a variant of quicksort developed by
1430:(as the AKS sorting network is), either by Cole's technique or by a related technique of simulating multiple computation paths (
840:, all performing the same sequence of operations on different memory addresses. If the test algorithm is a PRAM algorithm uses
588:
and count the number of particles on each side of the origin. If there are more particles on the left than on the right, then
833:
517:
of the line, and eventually they and their median will all be to the right of the origin. The problem is to compute the time
339:, the same algorithm can also be used as the test algorithm. However, many applications use other test algorithms (often,
1587:
Parametric search has been applied in the development of efficient algorithms for optimization problems, particularly in
238:
of the simulated algorithm is unknown. To simulate each comparison, the parametric search applies a second algorithm, a
1523:. In the case of Goodrich and Pszona, the algorithm is randomized, and obtains this time bound with high probability.
2041:
of two polygons, with the translation chosen to minimize the distance, can be found using parametric search in time
31:
2800:
2651:
2608:
51:
2271:
points in the
Euclidean plane, moving at constant velocities, the time at which the points obtain the smallest
1785:
1581:
1773:
1577:
2321:
2044:
1812:
1535:(binary search) can also be used to transform decision into optimization. In this method, one maintains an
1194:, and the number of parallel steps is logarithmic. Thus, simulating this algorithm sequentially takes time
2359:
2038:
1933:
1822:
1671:. Parametric-search based algorithms for constructing two-dimensional centerpoints were later improved to
1600:
1588:
1536:
55:
2325:
1923:
1678:
1608:
1549:
1427:
50:(does this optimization problem have a solution with quality better than some given threshold?) into an
218:. To simulate the algorithm, each of these comparisons or tests needs to be simulated, even though the
2742:
514:
498:
2364:
2278:
2003:
1892:
1451:
1305:
2717:
2153:
1379:
1360:
195:
118:
2163:
2864:
2786:
2759:
2732:
2705:
2633:
2594:
2567:
2485:
2422:
2034:
1927:
976:
calls to the decision algorithm. Thus, the total time for parametric search in this case becomes
836:(PRAM) model of parallel computation, where a collection of processors operate in synchrony on a
829:
731:, the simulation must determine, for each particle, whether its crossing time is before or after
344:
2646:
2501:
2442:
1737:
1488:
1197:
1147:
1011:
624:
591:
1270:
1235:
1069:
944:
2854:
2551:
2475:
2388:
2343:
1796:
1777:
1634:
124:
2844:
2836:
2809:
2768:
2689:
2660:
2617:
2576:
2543:
2516:
2467:
2404:
2369:
1532:
376:. Whenever the simulation reaches a step in which the test algorithm compares its parameter
47:
2821:
2782:
2701:
2672:
2629:
2590:
2565:
Cole, Richard (1987), "Slowing down sorting networks to obtain faster sorting algorithms",
2528:
2418:
2381:
2275:(and the diameter at that time) can be found using a variation of Cole's technique in time
979:
788:
761:
734:
707:
680:
520:
315:
285:
93:
2817:
2778:
2697:
2668:
2625:
2586:
2524:
2414:
2395:; Toledo, Sivan (1994), "Applications of parametric searching in geometric optimization",
2377:
2157:
1604:
1541:
1135:
1103:
340:
2798:
Reischuk, RĂĽdiger (1985), "Probabilistic parallel algorithms for sorting and selection",
2536:
Chan, Timothy M (1998), "Geometric applications of a randomized optimization technique",
2434:
1139:
816:
best known running time or gives the fastest known algorithm for more advanced problems.
2746:
416:, it cannot perform this step by doing a numerical comparison, as it does not know what
2757:(1983), "Applying parallel computation algorithms in the design of serial algorithms",
2754:
2254:
2227:
2207:
2128:
2108:
1983:
1872:
1614:
1177:
1157:
1112:
1049:
924:
903:
883:
863:
843:
657:
571:
551:
480:
459:
439:
419:
399:
379:
359:
265:
245:
221:
201:
177:
157:
73:
39:
20:
2721:
1611:
containing the centerpoint also contains a constant fraction of the input points. For
1302:
calls to the linear-time decision algorithm. Putting these time bounds together gives
513:
at different times. Initially the particles, and their median, are to the left of the
2879:
837:
54:(find the best solution). It is frequently used for solving optimization problems in
2709:
2489:
1560:
When only concerned with expected performance, a randomized optimization technique (
2868:
2832:
Proceedings of the
Eighteenth Annual Symposium on Computational Geometry (SoCG '02)
2790:
2637:
2598:
2537:
2392:
1800:
1572:
2829:
van
Oostrum, René; Veltkamp, Remco C. (2002), "Parametric search made practical",
2426:
1631:-dimensional spaces, the optimal fraction that can be achieved is always at least
1109:
In the case of the example problem of finding the crossing time of the median of
1672:
545:
2693:
2520:
2497:
1419:
1129:
moving particles, the sequential test algorithm can be replaced by a parallel
1815:
involves finding the longest line segment that lies entirely within a given
1356:
27:
2409:
312:
Since the decision algorithm itself necessarily behaves discontinuously at
2840:
2547:
2471:
704:
in quadratic total time. To simulate the decision algorithm for parameter
2272:
758:, and therefore whether it is to the left or right of the origin at time
2773:
2539:
Proceedings of the
Fourteenth Annual Symposium on Computational Geometry
343:
algorithms). Advanced versions of the parametric search technique use a
2463:
Proceedings of the 15th ACM Symposium on Theory of
Computing (STOC '83)
1816:
1781:
1130:
2849:
2581:
1552:
efforts are needed to make parametric search practical. Nevertheless,
1440:
combine Cole's theoretical improvement with the practical speedups of
621:, and if there are more particles on the right than on the left, then
1780:
for fitting a line to a set of points that is much less sensitive to
90:, as if it were being run with the (unknown) optimal solution value
2813:
2729:
Proc. 25th
Canadian Conference on Computational Geometry (CCCG 2013)
2664:
2621:
2373:
654:. Each step of this decision algorithm compares the input parameter
1154:). This can be interpreted as a PRAM algorithm in which the number
2737:
2509:
International Journal of Computational Geometry & Applications
1571:
1448:
in which the partitioning step partitions the input randomly into
194:
with other computed values, or by testing the sign of low-degree
2680:
Fernández-Baca, D. (2001), "On nonlinear parametric search",
2502:"Computing the Fréchet distance between two polygonal curves"
1930:
of the point set. Again, this problem can be solved in time
436:
is. Instead, it calls the decision algorithm with parameter
1789:
674:
to the time that one of the particles crosses the origin.
2649:(1989), "An optimal-time algorithm for slope selection",
1267:
batches of comparisons, each of which can be handled by
568:, one can compute the position of each particle at time
282:
is above, below, or equal to the optimal solution value
117:
as its input. This test algorithm is assumed to behave
2281:
2257:
2230:
2210:
2166:
2131:
2111:
2047:
2006:
1986:
1936:
1895:
1875:
1825:
1740:
1681:
1637:
1617:
1491:
1454:
1382:
1308:
1273:
1238:
1200:
1180:
1160:
1115:
1072:
1052:
1014:
982:
947:
927:
906:
886:
866:
846:
791:
764:
737:
710:
683:
660:
627:
594:
574:
554:
523:
483:
462:
442:
422:
402:
382:
362:
318:
288:
268:
248:
224:
204:
180:
160:
127:
96:
76:
66:
The basic idea of parametric search is to simulate a
1151:
2722:"Cole's parametric search technique made practical"
2645:Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.;
2146:
2027:
1916:
1592:
1553:
1527:
Comparison with binary search and randomized search
1441:
1352:
548:decision algorithm is easy to define: for any time
509:
2312:
2263:
2236:
2216:
2196:
2137:
2117:
2097:
2018:
1992:
1972:
1907:
1881:
1861:
1764:
1734:Parametric search can be used as the basis for an
1719:
1663:
1623:
1515:
1473:
1410:
1339:
1294:
1259:
1224:
1186:
1174:of processors is proportional to the input length
1166:
1121:
1093:
1058:
1038:
1000:
968:
933:
912:
892:
872:
852:
804:
777:
750:
723:
696:
666:
646:
613:
580:
560:
544:at which the median lies exactly on the origin. A
536:
489:
468:
448:
428:
408:
388:
368:
331:
301:
274:
254:
242:, that takes as input another numerical parameter
230:
210:
186:
166:
146:
109:
82:
2026:, using an algorithm based on parametric search (
1915:, using an algorithm based on parametric search (
2160:can be computed using parametric search in time
1805:
2350:(1993), "Ray shooting and parametric search",
2329:
1437:
1431:
1008:(for the simulation itself) plus the time for
2606:Cole, Richard (1988), "Parallel merge sort",
497:, this can again be simulated by passing the
8:
2244:are the numbers of segments of the curves (
2145:are the numbers of sides of the polygons (
70:that takes as input a numerical parameter
2848:
2772:
2736:
2580:
2408:
2363:
2295:
2280:
2256:
2229:
2209:
2165:
2130:
2110:
2077:
2067:
2046:
2005:
1985:
1951:
1947:
1935:
1894:
1874:
1840:
1836:
1824:
1739:
1702:
1692:
1680:
1641:
1636:
1616:
1490:
1461:
1453:
1393:
1381:
1322:
1307:
1272:
1237:
1232:for the simulation itself, together with
1199:
1179:
1159:
1114:
1071:
1051:
1013:
981:
946:
926:
905:
885:
865:
845:
796:
790:
769:
763:
742:
736:
715:
709:
688:
682:
659:
638:
626:
605:
593:
573:
553:
528:
522:
482:
461:
441:
421:
401:
381:
361:
323:
317:
293:
287:
267:
247:
223:
203:
179:
159:
138:
126:
101:
95:
75:
2835:, New York, NY, USA: ACM, pp. 1–9,
2245:
1445:
825:
505:
43:
2098:{\displaystyle O((mn)^{2}\log ^{3}mn)}
1046:calls to the decision algorithm (for
7:
1973:{\displaystyle O(n^{8/5+\epsilon })}
1862:{\displaystyle O(n^{8/5+\epsilon })}
1728:
1561:
1423:
1372:
1720:{\displaystyle O(n^{2}\log ^{4}n)}
154:, and to operate on its parameter
14:
2147:Agarwal, Sharir & Toledo 1994
2028:Agarwal, Sharir & Toledo 1994
1917:Agarwal, Sharir & Toledo 1994
1593:Agarwal, Sharir & Toledo 1994
1554:van Oostrum & Veltkamp (2002)
1442:van Oostrum & Veltkamp (2002)
1355:suggest using a parallel form of
1353:van Oostrum & Veltkamp (2002)
941:numerical comparisons using only
510:van Oostrum & Veltkamp (2002)
356:solution value as its parameter
1595:). They include the following:
1066:batches of comparisons, taking
16:Algorithmic optimization method
2313:{\displaystyle O(n\log ^{2}n)}
2307:
2285:
2191:
2170:
2092:
2064:
2054:
2051:
2019:{\displaystyle \epsilon >0}
1967:
1940:
1908:{\displaystyle \epsilon >0}
1856:
1829:
1759:
1744:
1714:
1685:
1658:
1646:
1510:
1495:
1474:{\displaystyle O({\sqrt {n}})}
1468:
1458:
1405:
1386:
1340:{\displaystyle O(n\log ^{2}n)}
1334:
1312:
1289:
1277:
1254:
1242:
1219:
1204:
1088:
1076:
1033:
1018:
995:
986:
963:
951:
834:parallel random-access machine
504:An example considered both by
262:, and that determines whether
174:only by simple comparisons of
26:In the design and analysis of
1:
1411:{\displaystyle O(\log ^{2}n)}
2197:{\displaystyle O(mn\log mn)}
1438:Goodrich & Pszona (2013)
1819:. It can be solved in time
1806:Agarwal & Matoušek 1993
38:is a technique invented by
2902:
2886:Combinatorial optimization
1765:{\displaystyle O(n\log n)}
1516:{\displaystyle O(n\log n)}
1225:{\displaystyle O(n\log n)}
1039:{\displaystyle O(T\log P)}
860:processors and takes time
647:{\displaystyle t>t_{0}}
614:{\displaystyle t<t_{0}}
32:combinatorial optimization
18:
2801:SIAM Journal on Computing
2694:10.1007/s00453-001-0001-2
2652:SIAM Journal on Computing
2609:SIAM Journal on Computing
2521:10.1142/S0218195995000064
2500:; Godau, Michael (1995),
2352:SIAM Journal on Computing
1607:is a point such that any
1295:{\displaystyle O(\log n)}
1260:{\displaystyle O(\log n)}
1094:{\displaystyle O(\log P)}
969:{\displaystyle O(\log P)}
351:Sequential test algorithm
2720:; Pszona, Paweł (2013),
2000:-sided polygons and any
1889:-sided polygons and any
1786:simple linear regression
1582:simple linear regression
19:Not to be confused with
1772:time algorithm for the
1664:{\displaystyle 1/(d+1)}
820:Parallel test algorithm
499:roots of the polynomial
147:{\displaystyle X=X^{*}}
2410:10.1006/jagm.1994.1038
2322:minimum enclosing ball
2314:
2265:
2238:
2218:
2198:
2139:
2119:
2099:
2020:
1994:
1974:
1909:
1883:
1863:
1766:
1721:
1665:
1625:
1589:computational geometry
1584:
1517:
1475:
1412:
1368:Desynchronized sorting
1341:
1296:
1261:
1226:
1188:
1168:
1123:
1095:
1060:
1040:
1002:
970:
935:
914:
894:
874:
854:
832:, for instance in the
806:
779:
752:
725:
698:
668:
648:
615:
582:
562:
538:
491:
470:
450:
430:
410:
390:
370:
333:
303:
276:
256:
232:
212:
188:
168:
148:
111:
84:
56:computational geometry
52:optimization algorithm
2841:10.1145/513400.513401
2548:10.1145/276884.276915
2472:10.1145/800061.808726
2397:Journal of Algorithms
2326:maximum spanning tree
2324:or the weight of the
2315:
2266:
2239:
2219:
2199:
2140:
2120:
2100:
2021:
1995:
1975:
1910:
1884:
1864:
1813:biggest stick problem
1767:
1722:
1666:
1626:
1575:
1550:algorithm engineering
1518:
1476:
1413:
1342:
1297:
1262:
1227:
1189:
1169:
1124:
1096:
1061:
1041:
1003:
1001:{\displaystyle O(PT)}
971:
936:
915:
895:
875:
855:
807:
805:{\displaystyle t_{0}}
780:
778:{\displaystyle t_{0}}
753:
751:{\displaystyle t_{0}}
726:
724:{\displaystyle t_{0}}
699:
697:{\displaystyle t_{0}}
669:
649:
616:
583:
563:
539:
537:{\displaystyle t_{0}}
492:
471:
451:
431:
411:
396:to some other number
391:
371:
334:
332:{\displaystyle X^{*}}
304:
302:{\displaystyle X^{*}}
277:
257:
233:
213:
189:
169:
149:
112:
110:{\displaystyle X^{*}}
85:
46:) for transforming a
2718:Goodrich, Michael T.
2542:, pp. 269–278,
2279:
2255:
2246:Alt & Godau 1995
2228:
2208:
2164:
2129:
2109:
2045:
2004:
1984:
1934:
1893:
1873:
1823:
1738:
1679:
1635:
1615:
1603:of a point set in a
1489:
1452:
1380:
1306:
1271:
1236:
1198:
1178:
1158:
1113:
1070:
1050:
1012:
980:
945:
925:
904:
884:
864:
844:
789:
762:
735:
708:
681:
658:
625:
592:
572:
552:
521:
481:
460:
440:
420:
400:
380:
360:
316:
286:
266:
246:
222:
202:
196:polynomial functions
178:
158:
125:
94:
74:
2774:10.1145/2157.322410
2747:2013arXiv1306.3000G
2330:Fernández-Baca 2001
1774:Theil–Sen estimator
1578:Theil–Sen estimator
1432:Fernández-Baca 2001
2760:Journal of the ACM
2568:Journal of the ACM
2460:sorting network",
2389:Agarwal, Pankaj K.
2344:Agarwal, Pankaj K.
2310:
2261:
2234:
2214:
2194:
2135:
2115:
2095:
2035:Hausdorff distance
2016:
1990:
1970:
1905:
1879:
1859:
1762:
1717:
1661:
1621:
1585:
1513:
1471:
1408:
1337:
1292:
1257:
1222:
1184:
1164:
1119:
1091:
1056:
1036:
998:
966:
931:
910:
890:
870:
850:
830:parallel algorithm
802:
775:
748:
721:
694:
664:
644:
611:
578:
558:
534:
487:
466:
446:
426:
406:
386:
366:
345:parallel algorithm
341:comparison sorting
329:
299:
272:
252:
240:decision algorithm
228:
208:
184:
164:
144:
107:
80:
48:decision algorithm
40:Nimrod Megiddo
2582:10.1145/7531.7537
2264:{\displaystyle n}
2237:{\displaystyle n}
2217:{\displaystyle m}
2138:{\displaystyle n}
2118:{\displaystyle m}
1993:{\displaystyle n}
1882:{\displaystyle n}
1797:computer graphics
1778:robust statistics
1624:{\displaystyle d}
1542:weakly polynomial
1466:
1187:{\displaystyle n}
1167:{\displaystyle P}
1122:{\displaystyle n}
1059:{\displaystyle T}
934:{\displaystyle P}
913:{\displaystyle P}
893:{\displaystyle T}
873:{\displaystyle T}
853:{\displaystyle P}
667:{\displaystyle t}
581:{\displaystyle t}
561:{\displaystyle t}
490:{\displaystyle X}
469:{\displaystyle Y}
449:{\displaystyle Y}
429:{\displaystyle X}
409:{\displaystyle Y}
389:{\displaystyle X}
369:{\displaystyle X}
275:{\displaystyle Y}
255:{\displaystyle Y}
231:{\displaystyle X}
211:{\displaystyle X}
187:{\displaystyle X}
167:{\displaystyle X}
83:{\displaystyle X}
36:parametric search
2893:
2871:
2852:
2824:
2793:
2776:
2749:
2740:
2726:
2712:
2675:
2647:Szemerédi, Endre
2640:
2601:
2584:
2560:
2531:
2506:
2492:
2466:, pp. 1–9,
2459:
2429:
2412:
2384:
2367:
2319:
2317:
2316:
2311:
2300:
2299:
2270:
2268:
2267:
2262:
2243:
2241:
2240:
2235:
2223:
2221:
2220:
2215:
2203:
2201:
2200:
2195:
2158:polygonal chains
2154:Fréchet distance
2144:
2142:
2141:
2136:
2124:
2122:
2121:
2116:
2104:
2102:
2101:
2096:
2082:
2081:
2072:
2071:
2025:
2023:
2022:
2017:
1999:
1997:
1996:
1991:
1979:
1977:
1976:
1971:
1966:
1965:
1955:
1914:
1912:
1911:
1906:
1888:
1886:
1885:
1880:
1868:
1866:
1865:
1860:
1855:
1854:
1844:
1790:Cole et al. 1989
1771:
1769:
1768:
1763:
1726:
1724:
1723:
1718:
1707:
1706:
1697:
1696:
1670:
1668:
1667:
1662:
1645:
1630:
1628:
1627:
1622:
1533:bisection method
1522:
1520:
1519:
1514:
1480:
1478:
1477:
1472:
1467:
1462:
1417:
1415:
1414:
1409:
1398:
1397:
1346:
1344:
1343:
1338:
1327:
1326:
1301:
1299:
1298:
1293:
1266:
1264:
1263:
1258:
1231:
1229:
1228:
1223:
1193:
1191:
1190:
1185:
1173:
1171:
1170:
1165:
1128:
1126:
1125:
1120:
1100:
1098:
1097:
1092:
1065:
1063:
1062:
1057:
1045:
1043:
1042:
1037:
1007:
1005:
1004:
999:
975:
973:
972:
967:
940:
938:
937:
932:
919:
917:
916:
911:
899:
897:
896:
891:
879:
877:
876:
871:
859:
857:
856:
851:
811:
809:
808:
803:
801:
800:
784:
782:
781:
776:
774:
773:
757:
755:
754:
749:
747:
746:
730:
728:
727:
722:
720:
719:
703:
701:
700:
695:
693:
692:
673:
671:
670:
665:
653:
651:
650:
645:
643:
642:
620:
618:
617:
612:
610:
609:
587:
585:
584:
579:
567:
565:
564:
559:
543:
541:
540:
535:
533:
532:
496:
494:
493:
488:
475:
473:
472:
467:
455:
453:
452:
447:
435:
433:
432:
427:
415:
413:
412:
407:
395:
393:
392:
387:
375:
373:
372:
367:
338:
336:
335:
330:
328:
327:
308:
306:
305:
300:
298:
297:
281:
279:
278:
273:
261:
259:
258:
253:
237:
235:
234:
229:
217:
215:
214:
209:
193:
191:
190:
185:
173:
171:
170:
165:
153:
151:
150:
145:
143:
142:
116:
114:
113:
108:
106:
105:
89:
87:
86:
81:
2901:
2900:
2896:
2895:
2894:
2892:
2891:
2890:
2876:
2875:
2861:
2828:
2814:10.1137/0214030
2797:
2755:Megiddo, Nimrod
2753:
2724:
2716:
2679:
2665:10.1137/0218055
2644:
2622:10.1137/0217049
2605:
2564:
2558:
2535:
2504:
2496:
2482:
2446:
2433:
2387:
2374:10.1137/0222051
2365:10.1.1.298.6047
2342:
2339:
2291:
2277:
2276:
2253:
2252:
2226:
2225:
2206:
2205:
2162:
2161:
2127:
2126:
2107:
2106:
2073:
2063:
2043:
2042:
2002:
2001:
1982:
1981:
1943:
1932:
1931:
1891:
1890:
1871:
1870:
1832:
1821:
1820:
1736:
1735:
1698:
1688:
1677:
1676:
1633:
1632:
1613:
1612:
1605:Euclidean space
1570:
1529:
1487:
1486:
1450:
1449:
1446:Reischuk (1985)
1389:
1378:
1377:
1370:
1318:
1304:
1303:
1269:
1268:
1234:
1233:
1196:
1195:
1176:
1175:
1156:
1155:
1136:sorting network
1111:
1110:
1104:polylogarithmic
1068:
1067:
1048:
1047:
1010:
1009:
978:
977:
943:
942:
923:
922:
902:
901:
882:
881:
862:
861:
842:
841:
822:
792:
787:
786:
765:
760:
759:
738:
733:
732:
711:
706:
705:
684:
679:
678:
656:
655:
634:
623:
622:
601:
590:
589:
570:
569:
550:
549:
524:
519:
518:
479:
478:
458:
457:
438:
437:
418:
417:
398:
397:
378:
377:
358:
357:
353:
319:
314:
313:
289:
284:
283:
264:
263:
244:
243:
220:
219:
200:
199:
176:
175:
156:
155:
134:
123:
122:
119:discontinuously
97:
92:
91:
72:
71:
64:
24:
17:
12:
11:
5:
2899:
2897:
2889:
2888:
2878:
2877:
2874:
2873:
2859:
2826:
2808:(2): 396–409,
2795:
2767:(4): 852–865,
2751:
2714:
2677:
2659:(4): 792–810,
2642:
2616:(4): 770–785,
2603:
2575:(1): 200–208,
2562:
2556:
2533:
2515:(1–2): 75–91,
2494:
2480:
2431:
2403:(3): 292–318,
2385:
2358:(4): 794–806,
2348:Matoušek, JiĹ™Ă
2338:
2335:
2334:
2333:
2309:
2306:
2303:
2298:
2294:
2290:
2287:
2284:
2260:
2249:
2233:
2213:
2193:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2150:
2134:
2114:
2094:
2091:
2088:
2085:
2080:
2076:
2070:
2066:
2062:
2059:
2056:
2053:
2050:
2031:
2015:
2012:
2009:
1989:
1969:
1964:
1961:
1958:
1954:
1950:
1946:
1942:
1939:
1920:
1904:
1901:
1898:
1878:
1858:
1853:
1850:
1847:
1843:
1839:
1835:
1831:
1828:
1809:
1793:
1776:, a method in
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1732:
1716:
1713:
1710:
1705:
1701:
1695:
1691:
1687:
1684:
1660:
1657:
1654:
1651:
1648:
1644:
1640:
1620:
1569:
1566:
1528:
1525:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1470:
1465:
1460:
1457:
1407:
1404:
1401:
1396:
1392:
1388:
1385:
1369:
1366:
1336:
1333:
1330:
1325:
1321:
1317:
1314:
1311:
1291:
1288:
1285:
1282:
1279:
1276:
1256:
1253:
1250:
1247:
1244:
1241:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1183:
1163:
1146:, and
1118:
1090:
1087:
1084:
1081:
1078:
1075:
1055:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
997:
994:
991:
988:
985:
965:
962:
959:
956:
953:
950:
930:
909:
889:
869:
849:
826:Megiddo (1983)
821:
818:
799:
795:
772:
768:
745:
741:
718:
714:
691:
687:
663:
641:
637:
633:
630:
608:
604:
600:
597:
577:
557:
531:
527:
506:Megiddo (1983)
486:
465:
445:
425:
405:
385:
365:
352:
349:
326:
322:
296:
292:
271:
251:
227:
207:
183:
163:
141:
137:
133:
130:
104:
100:
79:
68:test algorithm
63:
60:
21:Faceted search
15:
13:
10:
9:
6:
4:
3:
2:
2898:
2887:
2884:
2883:
2881:
2870:
2866:
2862:
2860:1-58113-504-1
2856:
2851:
2846:
2842:
2838:
2834:
2833:
2827:
2823:
2819:
2815:
2811:
2807:
2803:
2802:
2796:
2792:
2788:
2784:
2780:
2775:
2770:
2766:
2762:
2761:
2756:
2752:
2748:
2744:
2739:
2734:
2730:
2723:
2719:
2715:
2711:
2707:
2703:
2699:
2695:
2691:
2687:
2683:
2678:
2674:
2670:
2666:
2662:
2658:
2654:
2653:
2648:
2643:
2639:
2635:
2631:
2627:
2623:
2619:
2615:
2611:
2610:
2604:
2600:
2596:
2592:
2588:
2583:
2578:
2574:
2570:
2569:
2563:
2559:
2557:0-89791-973-4
2553:
2549:
2545:
2541:
2540:
2534:
2530:
2526:
2522:
2518:
2514:
2510:
2503:
2499:
2495:
2491:
2487:
2483:
2481:0-89791-099-0
2477:
2473:
2469:
2465:
2464:
2457:
2453:
2449:
2444:
2443:Szemerédi, E.
2440:
2436:
2432:
2428:
2424:
2420:
2416:
2411:
2406:
2402:
2398:
2394:
2393:Sharir, Micha
2390:
2386:
2383:
2379:
2375:
2371:
2366:
2361:
2357:
2353:
2349:
2345:
2341:
2340:
2336:
2331:
2327:
2323:
2304:
2301:
2296:
2292:
2288:
2282:
2274:
2258:
2250:
2247:
2231:
2211:
2188:
2185:
2182:
2179:
2176:
2173:
2167:
2159:
2155:
2151:
2148:
2132:
2112:
2089:
2086:
2083:
2078:
2074:
2068:
2060:
2057:
2048:
2040:
2036:
2032:
2029:
2013:
2010:
2007:
1987:
1962:
1959:
1956:
1952:
1948:
1944:
1937:
1929:
1925:
1921:
1918:
1902:
1899:
1896:
1876:
1851:
1848:
1845:
1841:
1837:
1833:
1826:
1818:
1814:
1810:
1807:
1802:
1798:
1794:
1791:
1787:
1783:
1779:
1775:
1756:
1753:
1750:
1747:
1741:
1733:
1730:
1711:
1708:
1703:
1699:
1693:
1689:
1682:
1674:
1655:
1652:
1649:
1642:
1638:
1618:
1610:
1606:
1602:
1598:
1597:
1596:
1594:
1590:
1583:
1579:
1574:
1567:
1565:
1563:
1558:
1555:
1551:
1545:
1543:
1538:
1534:
1526:
1524:
1507:
1504:
1501:
1498:
1492:
1483:
1463:
1455:
1447:
1443:
1439:
1435:
1433:
1429:
1425:
1422:algorithm of
1421:
1402:
1399:
1394:
1390:
1383:
1374:
1367:
1365:
1362:
1358:
1354:
1349:
1331:
1328:
1323:
1319:
1315:
1309:
1286:
1283:
1280:
1274:
1251:
1248:
1245:
1239:
1216:
1213:
1210:
1207:
1201:
1181:
1161:
1153:
1149:
1145:
1141:
1137:
1132:
1116:
1107:
1105:
1085:
1082:
1079:
1073:
1053:
1030:
1027:
1024:
1021:
1015:
992:
989:
983:
960:
957:
954:
948:
928:
907:
887:
867:
847:
839:
838:shared memory
835:
831:
827:
819:
817:
813:
797:
793:
770:
766:
743:
739:
716:
712:
689:
685:
675:
661:
639:
635:
631:
628:
606:
602:
598:
595:
575:
555:
547:
529:
525:
516:
511:
507:
502:
500:
484:
463:
443:
423:
403:
383:
363:
350:
348:
346:
342:
324:
320:
310:
294:
290:
269:
249:
241:
225:
205:
197:
181:
161:
139:
135:
131:
128:
120:
102:
98:
77:
69:
61:
59:
57:
53:
49:
45:
41:
37:
33:
29:
22:
2830:
2805:
2799:
2764:
2758:
2728:
2685:
2682:Algorithmica
2681:
2656:
2650:
2613:
2607:
2572:
2566:
2538:
2512:
2508:
2461:
2455:
2451:
2447:
2445:(1983), "An
2400:
2396:
2355:
2351:
2156:between two
1801:ray shooting
1586:
1580:compared to
1568:Applications
1559:
1546:
1544:algorithms.
1530:
1484:
1436:
1371:
1350:
1108:
823:
814:
676:
503:
354:
311:
239:
67:
65:
35:
25:
2688:(1): 1–11,
2498:Alt, Helmut
1673:linear time
1601:centerpoint
1424:Cole (1988)
1373:Cole (1987)
546:linear time
2850:1874/18869
2439:KomlĂłs, J.
2337:References
2039:translates
1609:half-space
1420:merge sort
1361:worst case
880:(that is,
28:algorithms
2738:1306.3000
2435:Ajtai, M.
2360:CiteSeerX
2302:
2183:
2084:
2008:ϵ
1963:ϵ
1928:roundness
1897:ϵ
1852:ϵ
1754:
1729:Cole 1987
1709:
1562:Chan 1998
1505:
1400:
1357:quicksort
1329:
1284:
1249:
1214:
1148:Szemerédi
1083:
1028:
958:
325:∗
295:∗
140:∗
103:∗
62:Technique
2880:Category
2710:20320912
2490:15311122
2273:diameter
2204:, where
2105:, where
2037:between
1782:outliers
1537:interval
2869:1551019
2822:0784745
2791:2212007
2783:0819134
2743:Bibcode
2702:1816864
2673:1004799
2638:2416667
2630:0953293
2599:2301419
2591:0882669
2529:1331177
2419:1300253
2382:1227762
1924:annulus
1817:polygon
1150: (
1131:sorting
42: (
2867:
2857:
2820:
2789:
2781:
2708:
2700:
2671:
2636:
2628:
2597:
2589:
2554:
2527:
2488:
2478:
2427:380722
2425:
2417:
2380:
2362:
1980:, for
1869:, for
1799:, the
1428:degree
1144:KomlĂłs
1142:,
515:origin
2865:S2CID
2787:S2CID
2733:arXiv
2725:(PDF)
2706:S2CID
2634:S2CID
2595:S2CID
2505:(PDF)
2486:S2CID
2423:S2CID
1784:than
1140:Ajtai
121:when
2855:ISBN
2552:ISBN
2476:ISBN
2454:log
2251:For
2224:and
2152:The
2125:and
2033:The
2011:>
1922:The
1900:>
1811:The
1576:The
1531:The
1152:1983
632:>
599:<
508:and
44:1983
30:for
2845:hdl
2837:doi
2810:doi
2769:doi
2690:doi
2661:doi
2618:doi
2577:doi
2544:doi
2517:doi
2468:doi
2405:doi
2370:doi
2293:log
2180:log
2075:log
1795:In
1751:log
1700:log
1502:log
1434:).
1391:log
1320:log
1281:log
1246:log
1211:log
1138:of
1080:log
1025:log
955:log
824:As
198:of
2882::
2863:,
2853:,
2843:,
2818:MR
2816:,
2806:14
2804:,
2785:,
2779:MR
2777:,
2765:30
2763:,
2741:,
2731:,
2727:,
2704:,
2698:MR
2696:,
2686:30
2684:,
2669:MR
2667:,
2657:18
2655:,
2632:,
2626:MR
2624:,
2614:17
2612:,
2593:,
2587:MR
2585:,
2573:34
2571:,
2550:,
2525:MR
2523:,
2511:,
2507:,
2484:,
2474:,
2441:;
2437:;
2421:,
2415:MR
2413:,
2401:17
2399:,
2391:;
2378:MR
2376:,
2368:,
2356:22
2354:,
2346:;
2332:).
2248:).
2149:).
2030:).
1919:).
1808:).
1792:).
1731:).
1599:A
309:.
58:.
34:,
2872:.
2847::
2839::
2825:.
2812::
2794:.
2771::
2750:.
2745::
2735::
2713:.
2692::
2676:.
2663::
2641:.
2620::
2602:.
2579::
2561:.
2546::
2532:.
2519::
2513:5
2493:.
2470::
2458:)
2456:n
2452:n
2450:(
2448:O
2430:.
2407::
2372::
2328:(
2308:)
2305:n
2297:2
2289:n
2286:(
2283:O
2259:n
2232:n
2212:m
2192:)
2189:n
2186:m
2177:n
2174:m
2171:(
2168:O
2133:n
2113:m
2093:)
2090:n
2087:m
2079:3
2069:2
2065:)
2061:n
2058:m
2055:(
2052:(
2049:O
2014:0
1988:n
1968:)
1960:+
1957:5
1953:/
1949:8
1945:n
1941:(
1938:O
1903:0
1877:n
1857:)
1849:+
1846:5
1842:/
1838:8
1834:n
1830:(
1827:O
1804:(
1788:(
1760:)
1757:n
1748:n
1745:(
1742:O
1727:(
1715:)
1712:n
1704:4
1694:2
1690:n
1686:(
1683:O
1659:)
1656:1
1653:+
1650:d
1647:(
1643:/
1639:1
1619:d
1591:(
1511:)
1508:n
1499:n
1496:(
1493:O
1469:)
1464:n
1459:(
1456:O
1406:)
1403:n
1395:2
1387:(
1384:O
1335:)
1332:n
1324:2
1316:n
1313:(
1310:O
1290:)
1287:n
1278:(
1275:O
1255:)
1252:n
1243:(
1240:O
1220:)
1217:n
1208:n
1205:(
1202:O
1182:n
1162:P
1117:n
1089:)
1086:P
1077:(
1074:O
1054:T
1034:)
1031:P
1022:T
1019:(
1016:O
996:)
993:T
990:P
987:(
984:O
964:)
961:P
952:(
949:O
929:P
908:P
888:T
868:T
848:P
798:0
794:t
771:0
767:t
744:0
740:t
717:0
713:t
690:0
686:t
662:t
640:0
636:t
629:t
607:0
603:t
596:t
576:t
556:t
530:0
526:t
485:X
464:Y
444:Y
424:X
404:Y
384:X
364:X
321:X
291:X
270:Y
250:Y
226:X
206:X
182:X
162:X
136:X
132:=
129:X
99:X
78:X
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.