4029:
as a binary search problem, searching for the x coordinate of the points among the x coordinates of the path vertices to determine which path edge might be above or below the query point. Thus, each point location query can be solved as an outer layer of binary search among the paths, each step of which itself performs a binary search among x coordinates of vertices. Fractional cascading can be used to speed up the time for the inner binary searches, reducing the total time per query to O(log
3941:
4028:
showed, this problem can be solved by finding a sequence of polygonal paths that stretch from left to right across the subdivision, and binary searching for the lowest of these paths that is above the query point. Testing whether the query point is above or below one of the paths can itself be solved
3987:
of the point set and the recursively-constructed convex layers of the remaining points. Within a single layer, the points inside the query half-plane may be found by performing a binary search for the half-plane boundary line's slope among the sorted sequence of convex polygon edge slopes, leading to
3823:
First, when an item is inserted or deleted at a node of the catalog graph, it must be placed within the augmented list associated with that node, and may cause changes to propagate to other nodes of the catalog graph. Instead of storing the augmented lists in arrays, they should be stored as binary
28:
for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by
3992:
along the polygon edges to find all other vertices inside the query half-plane. The whole half-plane range reporting problem may be solved by repeating this search procedure starting from the outermost layer and continuing inwards until reaching a layer that is disjoint from the query halfspace.
3792:, so that the total amount by which all lists are augmented remains linear in the input size. Each item in each augmented list stores with it the position of that item in the unaugmented list stored at the same vertex, and in each of the outgoing neighboring lists. In the simple example above,
3772:
in each of the ordered lists associated with the vertices of the path. For the simple example above, the catalog graph is itself a path, with just four nodes. It is possible for later vertices in the path to be determined dynamically as part of a query, in response to the results found by the
3895:
For each neighboring node in the catalog graph, a similar integer searching data structure for the numbers associated with the subset of the data propagated from the neighboring node. With this structure, and the mapping from items to integers, one can efficiently find for each element
3844:, with the selected items guaranteed to be spaced a constant number of positions apart in the full list, and such that an insertion or deletion into the augmented list associated with a node causes changes to propagate to other nodes for a fraction of the operations that is less than 1/
3827:
Second, an insertion or deletion may cause a change to the subset of the list associated with a node that is passed on to neighboring nodes of the catalog graph. It is no longer feasible, in the dynamic setting, for this subset to be chosen as the items at every
3868:
A mapping of the items in the augmented list of the node to small integers, such that the ordering of the positions in the augmented list is equivalent to the comparison ordering of the integers, and a reverse map from these integers back to the list items. The
3573:
3711:
3848:. In this way, the distribution of the data among the nodes satisfies the properties needed for the query algorithm to be fast, while guaranteeing that the average number of binary search tree operations per data insertion or deletion is constant.
3859:
among the input items from that node and among the augmented lists stored at neighboring nodes. However, this information would be too expensive to maintain in the dynamic setting. Inserting or deleting a single value
3799:
A query in this data structure consists of a standard binary search in the augmented list associated with the first vertex of the query path, together with simpler searches at each successive vertex of the path. If a
3820:, the list stored at each node of the catalog graph may change dynamically, by a sequence of updates in which list items are inserted and deleted. This causes several difficulties for the data structure.
3402:
61:. Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.
3578:
3971:
and listing all the points in the intersection. The problem is to structure the points in such a way that a query of this type may be answered efficiently in terms of the intersection size
483:
628:
3864:
could cause the indexes stored at an unbounded number of other values to change. Instead, dynamic versions of fractional cascading maintain several data structures for each node:
3993:
Fractional cascading speeds up the successive binary searches among the sequences of polygon edge slopes in each layer, leading to a data structure for this problem with space O(
161:
4017:. As in our example, this application involves binary searches in a linear sequence of lists (the nested sequence of the convex layers), so the catalog graph is just a path.
3788:, the lists associated with each vertex are augmented by a fraction of the items from each outgoing neighbor of the vertex; the fraction must be chosen to be smaller than 1/
3808:
steps of the position stored at the query result from the previous path vertex, and therefore may be found in constant time without having to perform a full binary search.
3368:
1537:
1066:
2898:
2742:
2237:
1401:
1359:
1234:
3281:
3228:
3148:
1854:
1734:
3068:
3738:
3397:
3195:
3115:
3042:
2995:
2945:
2856:
2789:
2700:
2653:
2606:
2559:
2512:
2465:
2429:
2382:
2335:
2288:
2195:
2144:
2048:
1996:
1944:
1884:
1801:
1701:
1674:
1647:
1620:
1593:
1433:
1317:
1270:
758:
390:
361:
332:
303:
114:
3884:
for the numbers associated with the input list of the node. With this structure, and the mapping from items to integers, one can efficiently find for each element
2097:
1566:
1152:
423:
273:
3327:
551:
247:
3301:
3248:
3168:
3088:
3015:
2968:
2918:
2829:
2809:
2762:
2673:
2626:
2579:
2532:
2485:
2402:
2355:
2308:
2261:
2168:
2117:
1821:
1774:
1754:
1493:
1473:
1453:
1290:
1192:
1172:
1126:
1106:
1086:
948:
925:
905:
885:
865:
845:
825:
805:
731:
711:
691:
671:
651:
571:
523:
503:
221:
201:
181:
87:
4149:
Proceedings of the IFIP TC6 WG6.1 & WG6.4 / IEEE ComSoc TC on
Gigabit Networking Sixth International Workshop on Protocols for High Speed Networks VI
4024:
in a monotone subdivision, that is, a partition of the plane into polygons such that any vertical line intersects any polygon in at most two points. As
3372:
In our example, the fractionally cascaded lists have a total of 25 elements, less than twice that of the original input. In general, the size of
1498:
Fractional cascading allows this same searching problem to be solved with time and space bounds meeting the best of both worlds: query time
3804:
fraction of items are used to augment the lists from each neighboring item, then each successive query result may be found within at most
4141:
4090:
4480:
Lakshman, T. V.; Stiliadis, D. (1998), "High-speed policy-based packet forwarding using efficient multi-dimensional range matching",
4482:
Proceedings of the ACM SIGCOMM '98 Conference on
Applications, Technologies, Architectures, and Protocols for Computer Communication
4084:"Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any Minkowski metric"
927:
in each of the original input lists (or the position after the end of the list if no such element exists), then we would have
4507:
4447:
4370:
4118:
396:
The simplest solution to this searching problem is just to store each list separately. If we do so, the space requirement is
3824:
search trees, so that these changes can be handled efficiently while still allowing binary searches of the augmented lists.
3944:
The convex layers of a point set, part of an efficient fractionally cascaded data structure for half-plane range reporting.
3855:
of the augmented list at each node of the catalog graph, the index of the result that would be obtained when searching for
4037:). In this application the catalog graph is a tree representing the possible search sequences of the outer binary search.
4618:
Yap, Chee; Zhu, Yunyue (2001), "Yet another look at fractional cascading: B-graphs with application to point location",
4645:
4396:
3568:{\displaystyle |L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,}
428:
69:
As a simple example of fractional cascading, consider the following problem. We are given as input a collection of
576:
4640:
4424:
3706:{\displaystyle \sum |M_{i}|=\sum |L_{i}|\left(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots \right)\leq 2n=O(n),}
3836:, as this subset would change too drastically after every update. Rather, a technique closely related to
4650:
3851:
Third, and most critically, the static fractional cascading data structure maintains, for each element
4275:
4232:
119:
3870:
2950:
More generally, for any data structure of this type, we perform a query by doing a binary search for
4334:
4207:
2608:
would return either the value 62 at position 3, or the value 44 one place earlier. A comparison of
4490:
4168:
4083:
3908:
These data structures allow dynamic fractional cascading to be performed at a time of O(log
3713:
as may be seen by regrouping the contributions to the total size coming from the same input list
3575:
as may easily be proven by induction. Therefore, the total size of the data structure is at most
3332:
1501:
1030:
3988:
the polygon vertex that is inside the query half-plane and farthest from its boundary, and then
2337:
would return either the value 79 at position 5, or the value 62 one place earlier. By comparing
4485:
4432:
Proc. of the 3rd
International Symposium on Information Processing in Sensor Networks (IPSN'04)
4329:
4314:
4202:
4152:
3953:
4187:
2861:
2705:
2200:
1364:
1322:
1197:
3757:
3253:
3200:
3120:
1826:
1706:
907:
are the positions (the first number has position 0) of the next element at least as large as
3047:
4388:
3716:
3375:
3173:
3093:
3020:
2973:
2923:
2834:
2767:
2678:
2631:
2584:
2537:
2490:
2434:
2407:
2360:
2313:
2266:
2173:
2122:
2026:
1974:
1922:
1862:
1779:
1679:
1652:
1625:
1598:
1571:
1406:
1295:
1239:
736:
633:
A second solution allows faster queries at the expense of more space: we may merge all the
368:
339:
310:
281:
92:
2076:
1542:
1131:
399:
252:
8:
4079:
3761:
3306:
528:
226:
4466:
4095:, Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, pp. 114–126,
2357:
to 62, and observing that it is smaller, we determine that the correct search result in
4570:
4538:
4513:
4453:
4376:
4298:
4271:
4255:
4228:
4124:
4096:
3900:
of the augmented list, a position within a constant number of steps of the location of
3881:
3286:
3233:
3153:
3073:
3000:
2953:
2903:
2814:
2794:
2747:
2658:
2611:
2564:
2517:
2470:
2387:
2340:
2293:
2246:
2153:
2102:
1806:
1759:
1739:
1478:
1458:
1438:
1275:
1177:
1157:
1111:
1091:
1071:
933:
910:
890:
870:
850:
830:
810:
763:
716:
696:
676:
656:
636:
556:
508:
488:
206:
186:
166:
72:
34:
4619:
4315:"Lower bounds for intersection searching and fractional cascading in higher dimension"
4503:
4443:
4366:
4114:
3989:
1756:
in this merged list, we store two numbers: the position resulting from searching for
4542:
4517:
4380:
4353:
Proceedings of the
Fourteenth Annual ACM Symposium on Theory of Computing – STOC '82
4302:
4259:
4591:
4574:
4562:
4530:
4495:
4457:
4435:
4411:
4356:
4339:
4310:
4290:
4267:
4247:
4224:
4212:
4183:
4164:
4128:
4106:
3840:
allows the selection of a fraction of data that is guaranteed to be smaller than 1/
30:
17:
4020:
Another application of fractional cascading in geometric data structures concerns
4110:
4075:
4053:
3959:
2811:
with 46 shows that the correct result is 79 and that the result of searching for
183:, and must process them so that we can perform binary searches for a query value
46:
1403:. However, this solution pays a high penalty in space complexity: it uses space
4621:
Proceedings of the 13th
Canadian Conference on Computational Geometry (CCCG'01)
4343:
4061:
4021:
3980:
3753:
3796:= 1, and we augmented each list with a 1/2 fraction of the neighboring items.
3760:
is labeled with an ordered list. A query in this data structure consists of a
4634:
4607:
4550:
4216:
4049:
3976:
3776:
To handle queries of this type, for a graph in which each vertex has at most
25:
4595:
4525:
Lueker, George S. (1978), "A data structure for orthogonal range queries",
4392:
4137:
4060:
use fractional cascading as a model for data distribution and retrieval in
3949:
505:
lists. The worst case for querying this structure occurs when each of the
4499:
4439:
4361:
3940:
4603:
3984:
4534:
1568:. The fractional cascading solution is to store a new sequence of lists
4566:
4294:
4251:
3968:
3329:
requires only a single comparison. Thus, the total time for a query is
2920:
in each of our four lists, by doing a binary search in the single list
4092:
Algorithms and Data
Structures, 10th International Workshop, WADS 2007
4048:
apply fractional cascading in the design of data structures for fast
3888:
of the augmented list, the item that would be found on searching for
2628:
with the smaller value 44 shows us that the correct search result in
4415:
3283:
or is a single step away from that correct result, so stepping from
4101:
2947:
followed by a single comparison in each of the successive lists.
2514:. The second "3" in 62 tells us that the approximate location of
3837:
2744:, and the "3" in 62 tells us that the result of searching for
1856:. For the data above, this would give us the following lists:
4351:
Dietz, F. Paul (1982), "Maintaining order in a linked list",
57:, with the idea of fractional sampling, which originated in
4423:
Gao, J.; Guibas, L. J.; Hershberger, J.; Zhang, L. (2004),
4142:"Space Decomposition Techniques for Fast Layer-4 Switching"
3904:
in the augmented list associated with the neighboring node.
3230:
that is either the correct result of the binary search for
2997:, and determining from the resulting value the position of
4074:
2791:
is either 79 at position 3 or 46 at position 2; comparing
2073:
Suppose we wish to perform a query in this structure, for
4422:
4355:, Association for Computing Machinery, pp. 122–127,
4057:
3975:. One structure that can be used for this purpose is the
485:, as we must perform a separate binary search in each of
4553:; Näher, Stefan (1990), "Dynamic fractional cascading",
4387:
4025:
3920:
in the catalog graph to be performed in time O(log
2384:
is 62. The first "3" in 62 tells us that the search for
4425:"Fractionally cascaded information in a sensor network"
4233:"Fractional cascading: I. A data structuring technique"
4135:
4045:
4582:
Sen, S. D. (1995), "Fractional cascading revisited",
4169:"Filtering search: A new approach to query-answering"
3948:
Typical applications of fractional cascading involve
3719:
3581:
3405:
3378:
3335:
3309:
3289:
3256:
3236:
3203:
3176:
3156:
3123:
3096:
3076:
3050:
3023:
3003:
2976:
2956:
2926:
2906:
2864:
2837:
2817:
2797:
2770:
2750:
2708:
2681:
2661:
2634:
2614:
2587:
2567:
2540:
2520:
2493:
2473:
2437:
2410:
2390:
2363:
2343:
2316:
2296:
2269:
2249:
2203:
2176:
2156:
2125:
2105:
2079:
2029:
1977:
1925:
1865:
1829:
1809:
1782:
1762:
1742:
1709:
1682:
1655:
1628:
1601:
1574:
1545:
1504:
1481:
1461:
1441:
1409:
1367:
1325:
1298:
1278:
1242:
1200:
1180:
1160:
1134:
1114:
1094:
1074:
1033:
936:
913:
893:
873:
853:
833:
813:
766:
739:
719:
699:
679:
659:
639:
579:
559:
531:
511:
491:
431:
402:
371:
342:
313:
284:
255:
229:
209:
189:
169:
122:
95:
75:
3768:; the data structure must determine the position of
2561:
is position 3. More precisely, binary searching for
2290:
is position 5. More precisely, binary searching for
1194:
finds the item 62, from which we return the results
4474:, Univ. of Maryland, Tech. Report UMIACS-TR-2003-71
4005:). The data structure may be constructed in time O(
3877:
allows this numbering to be maintained efficiently.
760:. If we describe an element of this merged list as
4397:"Optimal point location in a monotone subdivision"
3732:
3705:
3567:
3391:
3362:
3321:
3295:
3275:
3242:
3222:
3189:
3162:
3142:
3109:
3082:
3062:
3036:
3009:
2989:
2962:
2939:
2912:
2892:
2850:
2823:
2803:
2783:
2756:
2736:
2694:
2667:
2655:is 62. The "2" in 62 tells us that the search for
2647:
2620:
2600:
2573:
2553:
2526:
2506:
2479:
2459:
2423:
2396:
2376:
2349:
2329:
2302:
2282:
2255:
2231:
2189:
2162:
2138:
2111:
2091:
2042:
1990:
1938:
1878:
1848:
1815:
1795:
1768:
1748:
1728:
1695:
1668:
1641:
1614:
1587:
1560:
1531:
1487:
1467:
1447:
1427:
1395:
1353:
1311:
1284:
1264:
1228:
1186:
1166:
1146:
1120:
1100:
1080:
1060:
942:
919:
899:
879:
859:
839:
819:
799:
752:
725:
705:
685:
665:
645:
622:
565:
545:
517:
497:
477:
417:
384:
355:
326:
297:
267:
241:
215:
195:
175:
155:
108:
81:
45:), combined the idea of cascading, originating in
4479:
4041:
4632:
4527:Proc. 19th Symp. Foundations of Computer Science
4266:
4223:
3912:) per insertion or deletion, and a sequence of
3811:
3748:In general, fractional cascading begins with a
1108:and then report the results stored at the item
573:binary searches involved in a query takes time
42:
38:
4468:Fast fractional cascading and its applications
3880:An integer searching data structure such as a
2150:. The "1" in 64, tells us that the search for
1803:and the position resulting from searching for
4609:Predicate-oriented database search algorithms
4549:
615:
585:
478:{\displaystyle O{\bigl (}k\log(n/k){\bigr )}}
470:
437:
3150:. The value associated with the position of
1027:This merged solution allows a query in time
623:{\displaystyle O{\bigl (}\log(n/k){\bigr )}}
4309:
3979:of the input point set, a family of nested
3916:binary searches following a path of length
2099:. We first do a standard binary search for
2243:tells us that the approximate location of
4489:
4360:
4333:
4206:
4100:
24:is a technique to speed up a sequence of
4276:"Fractional cascading: II. Applications"
4182:
4163:
4026:Edelsbrunner, Guibas & Stolfi (1986)
4014:
3939:
58:
4602:
4464:
4322:Journal of Computer and System Sciences
4195:IEEE Transactions on Information Theory
3963:: that is, intersecting a fixed set of
3956:. For example, consider the problem of
3773:searches in earlier parts of the path.
1128:found by this search. For instance, if
713:a list of the results of searching for
116:of numbers, such that the total length
54:
4633:
4617:
4524:
4465:JaJa, Joseph F.; Shi, Qingmin (2003),
4046:Buddhikot, Suri & Waldvogel (1999)
4033:) using a data structure with space O(
3743:
50:
4350:
4188:"On the convex layers of a point set"
3874:
425:, but the time to perform a query is
4581:
1595:. The final list in this sequence,
13:
4612:, Ph.D. thesis, Harvard University
3832:th position of the list, for some
3399:in this data structure is at most
14:
4662:
3784:outgoing edges for some constant
4151:, pp. 25–42, archived from
156:{\displaystyle \sum _{i}|L_{i}|}
4042:Lakshman & Stiliadis (1998)
4040:Beyond computational geometry,
3935:
3764:in the graph and a query value
3070:, we use the known position of
673:, and associate with each item
3697:
3691:
3627:
3612:
3601:
3586:
3552:
3531:
3500:
3479:
3461:
3440:
3422:
3407:
3357:
3339:
2881:
2875:
2725:
2719:
2454:
2448:
2220:
2214:
1555:
1549:
1526:
1508:
1422:
1413:
1384:
1378:
1342:
1336:
1272:(a flag value indicating that
1259:
1253:
1217:
1211:
1055:
1037:
794:
770:
610:
596:
465:
451:
412:
406:
149:
134:
1:
4067:
733:in each of the smaller lists
653:lists into a single big list
4140:; Waldvogel, Marcel (1999),
4111:10.1007/978-3-540-73951-7_11
3997:) and query time O(log
3818:dynamic fractional cascading
3812:Dynamic fractional cascading
2467:, a flag value meaning that
1703:with every second item from
7:
3363:{\displaystyle O(k+\log n)}
1532:{\displaystyle O(k+\log n)}
1061:{\displaystyle O(k+\log n)}
827:is the numerical value and
43:Chazelle & Guibas 1986b
39:Chazelle & Guibas 1986a
10:
4667:
4344:10.1016/j.jcss.2003.07.003
4082:; Polu, Stanislas (2007),
3740:together with each other.
223:lists. For instance, with
64:
4646:Geometric data structures
4404:SIAM Journal on Computing
4529:, IEEE, pp. 28–34,
4217:10.1109/TIT.1985.1057060
3928: log log
3197:points to a position in
3117:to find its position in
2893:{\displaystyle L_{4}=79}
2737:{\displaystyle L_{3}=62}
2487:is past the end of list
2232:{\displaystyle L_{1}=64}
1396:{\displaystyle L_{4}=79}
1354:{\displaystyle L_{3}=62}
1229:{\displaystyle L_{1}=64}
3276:{\displaystyle M_{i+1}}
3223:{\displaystyle M_{i+1}}
3143:{\displaystyle M_{i+1}}
1849:{\displaystyle M_{i+1}}
1729:{\displaystyle M_{i+1}}
4596:10.1006/jagm.1995.1032
4136:Buddhikot, Milind M.;
3990:sequentially searching
3954:computational geometry
3945:
3734:
3707:
3569:
3393:
3364:
3323:
3297:
3277:
3244:
3224:
3191:
3164:
3144:
3111:
3084:
3064:
3063:{\displaystyle i>1}
3038:
3011:
2991:
2964:
2941:
2914:
2900:. Thus, we have found
2894:
2852:
2825:
2805:
2785:
2758:
2738:
2696:
2669:
2649:
2622:
2602:
2575:
2555:
2528:
2508:
2481:
2461:
2425:
2398:
2378:
2351:
2331:
2304:
2284:
2257:
2233:
2191:
2164:
2140:
2113:
2093:
2044:
1992:
1940:
1880:
1850:
1817:
1797:
1770:
1750:
1730:
1697:
1670:
1643:
1616:
1589:
1562:
1533:
1489:
1469:
1449:
1429:
1397:
1355:
1313:
1286:
1266:
1230:
1188:
1168:
1148:
1122:
1102:
1082:
1062:
944:
921:
901:
881:
861:
841:
821:
801:
754:
727:
707:
687:
667:
647:
624:
567:
547:
519:
499:
479:
419:
386:
357:
328:
299:
269:
243:
217:
197:
177:
157:
110:
83:
4641:Graph data structures
4584:Journal of Algorithms
4500:10.1145/285237.285283
4440:10.1145/984622.984668
4362:10.1145/800070.802184
4013:) by an algorithm of
3943:
3780:incoming and at most
3735:
3733:{\displaystyle L_{i}}
3708:
3570:
3394:
3392:{\displaystyle M_{i}}
3365:
3324:
3298:
3278:
3245:
3225:
3192:
3190:{\displaystyle M_{i}}
3165:
3145:
3112:
3110:{\displaystyle M_{i}}
3085:
3065:
3039:
3037:{\displaystyle L_{1}}
3012:
2992:
2990:{\displaystyle M_{1}}
2965:
2942:
2940:{\displaystyle M_{1}}
2915:
2895:
2853:
2851:{\displaystyle L_{4}}
2826:
2806:
2786:
2784:{\displaystyle M_{4}}
2759:
2739:
2697:
2695:{\displaystyle L_{3}}
2670:
2650:
2648:{\displaystyle M_{3}}
2623:
2603:
2601:{\displaystyle M_{3}}
2576:
2556:
2554:{\displaystyle M_{3}}
2529:
2509:
2507:{\displaystyle L_{2}}
2482:
2462:
2460:{\displaystyle L_{2}}
2426:
2424:{\displaystyle L_{2}}
2399:
2379:
2377:{\displaystyle M_{2}}
2352:
2332:
2330:{\displaystyle M_{2}}
2305:
2285:
2283:{\displaystyle M_{2}}
2258:
2234:
2192:
2190:{\displaystyle L_{1}}
2165:
2141:
2139:{\displaystyle M_{1}}
2114:
2094:
2045:
2043:{\displaystyle M_{4}}
1993:
1991:{\displaystyle M_{3}}
1941:
1939:{\displaystyle M_{2}}
1881:
1879:{\displaystyle M_{1}}
1851:
1818:
1798:
1796:{\displaystyle L_{i}}
1771:
1751:
1731:
1698:
1696:{\displaystyle L_{i}}
1676:is formed by merging
1671:
1669:{\displaystyle M_{i}}
1644:
1642:{\displaystyle L_{k}}
1617:
1615:{\displaystyle M_{k}}
1590:
1588:{\displaystyle M_{i}}
1563:
1534:
1490:
1475:must store a list of
1470:
1450:
1430:
1428:{\displaystyle O(kn)}
1398:
1356:
1314:
1312:{\displaystyle L_{2}}
1287:
1267:
1265:{\displaystyle L_{2}}
1231:
1189:
1169:
1149:
1123:
1103:
1083:
1063:
945:
922:
902:
882:
862:
842:
822:
802:
755:
753:{\displaystyle L_{i}}
728:
708:
688:
668:
648:
625:
568:
548:
525:lists has equal size
520:
500:
480:
420:
387:
385:{\displaystyle L_{4}}
358:
356:{\displaystyle L_{3}}
329:
327:{\displaystyle L_{2}}
300:
298:{\displaystyle L_{1}}
270:
244:
218:
198:
178:
158:
111:
109:{\displaystyle L_{i}}
84:
4484:, pp. 203–214,
4434:, pp. 311–319,
4313:; Liu, Ding (2004),
4080:Goodrich, Michael T.
3967:points with a query
3717:
3579:
3403:
3376:
3333:
3307:
3287:
3254:
3234:
3201:
3174:
3154:
3121:
3094:
3074:
3048:
3021:
3001:
2974:
2954:
2924:
2904:
2862:
2835:
2815:
2795:
2768:
2748:
2706:
2679:
2659:
2632:
2612:
2585:
2565:
2538:
2518:
2491:
2471:
2435:
2408:
2388:
2361:
2341:
2314:
2294:
2267:
2247:
2201:
2174:
2154:
2146:, finding the value
2123:
2103:
2092:{\displaystyle q=50}
2077:
2027:
1975:
1923:
1863:
1827:
1807:
1780:
1760:
1740:
1707:
1680:
1653:
1649:; each earlier list
1626:
1599:
1572:
1561:{\displaystyle O(n)}
1543:
1502:
1479:
1459:
1439:
1407:
1365:
1323:
1296:
1276:
1240:
1198:
1178:
1158:
1147:{\displaystyle q=50}
1132:
1112:
1092:
1072:
1068:: simply search for
1031:
934:
911:
891:
871:
851:
831:
811:
764:
737:
717:
697:
677:
657:
637:
577:
557:
529:
509:
489:
429:
418:{\displaystyle O(n)}
400:
392:= 11, 35, 46, 79, 81
369:
340:
311:
305:= 24, 64, 65, 80, 93
282:
268:{\displaystyle n=17}
253:
227:
207:
187:
167:
120:
93:
73:
22:fractional cascading
4535:10.1109/SFCS.1978.1
4272:Guibas, Leonidas J.
4229:Guibas, Leonidas J.
4078:; Blanton, Marina;
4076:Atallah, Mikhail J.
3952:data structures in
3744:The general problem
3322:{\displaystyle i+1}
1292:is past the end of
546:{\displaystyle n/k}
242:{\displaystyle k=4}
49:data structures of
4624:, pp. 173–176
4567:10.1007/BF01840386
4295:10.1007/BF01840441
4252:10.1007/BF01840440
4176:Proc. 24 IEEE FOCS
3983:consisting of the
3946:
3892:in the input list.
3882:van Emde Boas tree
3730:
3703:
3565:
3389:
3360:
3319:
3293:
3273:
3240:
3220:
3187:
3160:
3140:
3107:
3080:
3060:
3034:
3007:
2987:
2960:
2937:
2910:
2890:
2848:
2821:
2801:
2781:
2754:
2734:
2692:
2665:
2645:
2618:
2598:
2571:
2551:
2524:
2504:
2477:
2457:
2421:
2394:
2374:
2347:
2327:
2300:
2280:
2253:
2229:
2187:
2160:
2136:
2109:
2089:
2040:
1988:
1936:
1876:
1846:
1813:
1793:
1766:
1746:
1726:
1693:
1666:
1639:
1612:
1585:
1558:
1529:
1485:
1465:
1445:
1425:
1393:
1351:
1309:
1282:
1262:
1226:
1184:
1164:
1144:
1118:
1098:
1078:
1058:
940:
917:
897:
877:
857:
837:
817:
797:
750:
723:
703:
683:
663:
643:
620:
563:
543:
515:
495:
475:
415:
382:
353:
324:
295:
265:
239:
213:
193:
173:
153:
132:
106:
79:
4651:Search algorithms
4509:978-1-58113-003-4
4449:978-1-58113-846-7
4391:; Guibas, L. J.;
4372:978-0-89791-070-5
4311:Chazelle, Bernard
4268:Chazelle, Bernard
4225:Chazelle, Bernard
4184:Chazelle, Bernard
4165:Chazelle, Bernard
4120:978-3-540-73948-7
4058:Gao et al. (2004)
3871:order-maintenance
3663:
3650:
3528:
3476:
3437:
3296:{\displaystyle i}
3243:{\displaystyle q}
3163:{\displaystyle q}
3083:{\displaystyle q}
3044:. Then, for each
3010:{\displaystyle q}
2963:{\displaystyle q}
2913:{\displaystyle q}
2824:{\displaystyle q}
2804:{\displaystyle q}
2757:{\displaystyle q}
2668:{\displaystyle q}
2621:{\displaystyle q}
2574:{\displaystyle q}
2527:{\displaystyle q}
2480:{\displaystyle q}
2397:{\displaystyle q}
2350:{\displaystyle q}
2303:{\displaystyle q}
2256:{\displaystyle q}
2163:{\displaystyle q}
2112:{\displaystyle q}
1816:{\displaystyle x}
1769:{\displaystyle x}
1749:{\displaystyle x}
1736:. With each item
1495:search results.
1488:{\displaystyle k}
1468:{\displaystyle L}
1448:{\displaystyle n}
1285:{\displaystyle q}
1187:{\displaystyle L}
1167:{\displaystyle q}
1121:{\displaystyle x}
1101:{\displaystyle L}
1081:{\displaystyle q}
943:{\displaystyle L}
920:{\displaystyle x}
900:{\displaystyle d}
880:{\displaystyle c}
860:{\displaystyle b}
840:{\displaystyle a}
820:{\displaystyle x}
800:{\displaystyle x}
726:{\displaystyle x}
706:{\displaystyle L}
686:{\displaystyle x}
666:{\displaystyle L}
646:{\displaystyle k}
566:{\displaystyle k}
553:, so each of the
518:{\displaystyle k}
498:{\displaystyle k}
216:{\displaystyle k}
196:{\displaystyle q}
176:{\displaystyle n}
123:
82:{\displaystyle k}
4658:
4625:
4613:
4598:
4577:
4545:
4520:
4493:
4475:
4473:
4460:
4429:
4418:
4401:
4389:Edelsbrunner, H.
4383:
4364:
4346:
4337:
4319:
4305:
4289:(1–4): 163–191,
4280:
4262:
4246:(1–4): 133–162,
4237:
4219:
4210:
4192:
4178:
4173:
4159:
4157:
4146:
4131:
4104:
4088:
4054:internet routers
4050:packet filtering
3739:
3737:
3736:
3731:
3729:
3728:
3712:
3710:
3709:
3704:
3675:
3671:
3664:
3656:
3651:
3643:
3630:
3625:
3624:
3615:
3604:
3599:
3598:
3589:
3574:
3572:
3571:
3566:
3555:
3550:
3549:
3534:
3529:
3527:
3526:
3514:
3503:
3498:
3497:
3482:
3477:
3469:
3464:
3459:
3458:
3443:
3438:
3430:
3425:
3420:
3419:
3410:
3398:
3396:
3395:
3390:
3388:
3387:
3369:
3367:
3366:
3361:
3328:
3326:
3325:
3320:
3302:
3300:
3299:
3294:
3282:
3280:
3279:
3274:
3272:
3271:
3249:
3247:
3246:
3241:
3229:
3227:
3226:
3221:
3219:
3218:
3196:
3194:
3193:
3188:
3186:
3185:
3169:
3167:
3166:
3161:
3149:
3147:
3146:
3141:
3139:
3138:
3116:
3114:
3113:
3108:
3106:
3105:
3089:
3087:
3086:
3081:
3069:
3067:
3066:
3061:
3043:
3041:
3040:
3035:
3033:
3032:
3016:
3014:
3013:
3008:
2996:
2994:
2993:
2988:
2986:
2985:
2969:
2967:
2966:
2961:
2946:
2944:
2943:
2938:
2936:
2935:
2919:
2917:
2916:
2911:
2899:
2897:
2896:
2891:
2874:
2873:
2857:
2855:
2854:
2849:
2847:
2846:
2830:
2828:
2827:
2822:
2810:
2808:
2807:
2802:
2790:
2788:
2787:
2782:
2780:
2779:
2763:
2761:
2760:
2755:
2743:
2741:
2740:
2735:
2718:
2717:
2701:
2699:
2698:
2693:
2691:
2690:
2674:
2672:
2671:
2666:
2654:
2652:
2651:
2646:
2644:
2643:
2627:
2625:
2624:
2619:
2607:
2605:
2604:
2599:
2597:
2596:
2580:
2578:
2577:
2572:
2560:
2558:
2557:
2552:
2550:
2549:
2533:
2531:
2530:
2525:
2513:
2511:
2510:
2505:
2503:
2502:
2486:
2484:
2483:
2478:
2466:
2464:
2463:
2458:
2447:
2446:
2430:
2428:
2427:
2422:
2420:
2419:
2403:
2401:
2400:
2395:
2383:
2381:
2380:
2375:
2373:
2372:
2356:
2354:
2353:
2348:
2336:
2334:
2333:
2328:
2326:
2325:
2309:
2307:
2306:
2301:
2289:
2287:
2286:
2281:
2279:
2278:
2262:
2260:
2259:
2254:
2238:
2236:
2235:
2230:
2213:
2212:
2196:
2194:
2193:
2188:
2186:
2185:
2169:
2167:
2166:
2161:
2145:
2143:
2142:
2137:
2135:
2134:
2118:
2116:
2115:
2110:
2098:
2096:
2095:
2090:
2049:
2047:
2046:
2041:
2039:
2038:
1997:
1995:
1994:
1989:
1987:
1986:
1945:
1943:
1942:
1937:
1935:
1934:
1885:
1883:
1882:
1877:
1875:
1874:
1855:
1853:
1852:
1847:
1845:
1844:
1822:
1820:
1819:
1814:
1802:
1800:
1799:
1794:
1792:
1791:
1775:
1773:
1772:
1767:
1755:
1753:
1752:
1747:
1735:
1733:
1732:
1727:
1725:
1724:
1702:
1700:
1699:
1694:
1692:
1691:
1675:
1673:
1672:
1667:
1665:
1664:
1648:
1646:
1645:
1640:
1638:
1637:
1621:
1619:
1618:
1613:
1611:
1610:
1594:
1592:
1591:
1586:
1584:
1583:
1567:
1565:
1564:
1559:
1538:
1536:
1535:
1530:
1494:
1492:
1491:
1486:
1474:
1472:
1471:
1466:
1454:
1452:
1451:
1446:
1434:
1432:
1431:
1426:
1402:
1400:
1399:
1394:
1377:
1376:
1360:
1358:
1357:
1352:
1335:
1334:
1318:
1316:
1315:
1310:
1308:
1307:
1291:
1289:
1288:
1283:
1271:
1269:
1268:
1263:
1252:
1251:
1235:
1233:
1232:
1227:
1210:
1209:
1193:
1191:
1190:
1185:
1173:
1171:
1170:
1165:
1154:, searching for
1153:
1151:
1150:
1145:
1127:
1125:
1124:
1119:
1107:
1105:
1104:
1099:
1087:
1085:
1084:
1079:
1067:
1065:
1064:
1059:
949:
947:
946:
941:
926:
924:
923:
918:
906:
904:
903:
898:
886:
884:
883:
878:
866:
864:
863:
858:
846:
844:
843:
838:
826:
824:
823:
818:
806:
804:
803:
798:
759:
757:
756:
751:
749:
748:
732:
730:
729:
724:
712:
710:
709:
704:
692:
690:
689:
684:
672:
670:
669:
664:
652:
650:
649:
644:
629:
627:
626:
621:
619:
618:
606:
589:
588:
572:
570:
569:
564:
552:
550:
549:
544:
539:
524:
522:
521:
516:
504:
502:
501:
496:
484:
482:
481:
476:
474:
473:
461:
441:
440:
424:
422:
421:
416:
391:
389:
388:
383:
381:
380:
363:= 13, 44, 62, 66
362:
360:
359:
354:
352:
351:
333:
331:
330:
325:
323:
322:
304:
302:
301:
296:
294:
293:
274:
272:
271:
266:
248:
246:
245:
240:
222:
220:
219:
214:
202:
200:
199:
194:
182:
180:
179:
174:
163:of all lists is
162:
160:
159:
154:
152:
147:
146:
137:
131:
115:
113:
112:
107:
105:
104:
88:
86:
85:
80:
18:computer science
4666:
4665:
4661:
4660:
4659:
4657:
4656:
4655:
4631:
4630:
4629:
4510:
4471:
4450:
4427:
4416:10.1137/0215023
4399:
4373:
4335:10.1.1.298.7772
4317:
4278:
4235:
4208:10.1.1.113.8709
4190:
4171:
4155:
4144:
4121:
4086:
4070:
4062:sensor networks
4015:Chazelle (1985)
4009: log
3981:convex polygons
3960:range reporting
3938:
3814:
3746:
3724:
3720:
3718:
3715:
3714:
3655:
3642:
3635:
3631:
3626:
3620:
3616:
3611:
3600:
3594:
3590:
3585:
3580:
3577:
3576:
3551:
3539:
3535:
3530:
3522:
3518:
3513:
3499:
3487:
3483:
3478:
3468:
3460:
3448:
3444:
3439:
3429:
3421:
3415:
3411:
3406:
3404:
3401:
3400:
3383:
3379:
3377:
3374:
3373:
3334:
3331:
3330:
3308:
3305:
3304:
3288:
3285:
3284:
3261:
3257:
3255:
3252:
3251:
3235:
3232:
3231:
3208:
3204:
3202:
3199:
3198:
3181:
3177:
3175:
3172:
3171:
3155:
3152:
3151:
3128:
3124:
3122:
3119:
3118:
3101:
3097:
3095:
3092:
3091:
3075:
3072:
3071:
3049:
3046:
3045:
3028:
3024:
3022:
3019:
3018:
3002:
2999:
2998:
2981:
2977:
2975:
2972:
2971:
2955:
2952:
2951:
2931:
2927:
2925:
2922:
2921:
2905:
2902:
2901:
2869:
2865:
2863:
2860:
2859:
2842:
2838:
2836:
2833:
2832:
2816:
2813:
2812:
2796:
2793:
2792:
2775:
2771:
2769:
2766:
2765:
2749:
2746:
2745:
2713:
2709:
2707:
2704:
2703:
2686:
2682:
2680:
2677:
2676:
2660:
2657:
2656:
2639:
2635:
2633:
2630:
2629:
2613:
2610:
2609:
2592:
2588:
2586:
2583:
2582:
2566:
2563:
2562:
2545:
2541:
2539:
2536:
2535:
2519:
2516:
2515:
2498:
2494:
2492:
2489:
2488:
2472:
2469:
2468:
2442:
2438:
2436:
2433:
2432:
2415:
2411:
2409:
2406:
2405:
2389:
2386:
2385:
2368:
2364:
2362:
2359:
2358:
2342:
2339:
2338:
2321:
2317:
2315:
2312:
2311:
2295:
2292:
2291:
2274:
2270:
2268:
2265:
2264:
2248:
2245:
2244:
2208:
2204:
2202:
2199:
2198:
2181:
2177:
2175:
2172:
2171:
2155:
2152:
2151:
2130:
2126:
2124:
2121:
2120:
2104:
2101:
2100:
2078:
2075:
2074:
2034:
2030:
2028:
2025:
2024:
1982:
1978:
1976:
1973:
1972:
1930:
1926:
1924:
1921:
1920:
1870:
1866:
1864:
1861:
1860:
1834:
1830:
1828:
1825:
1824:
1808:
1805:
1804:
1787:
1783:
1781:
1778:
1777:
1761:
1758:
1757:
1741:
1738:
1737:
1714:
1710:
1708:
1705:
1704:
1687:
1683:
1681:
1678:
1677:
1660:
1656:
1654:
1651:
1650:
1633:
1629:
1627:
1624:
1623:
1606:
1602:
1600:
1597:
1596:
1579:
1575:
1573:
1570:
1569:
1544:
1541:
1540:
1503:
1500:
1499:
1480:
1477:
1476:
1460:
1457:
1456:
1440:
1437:
1436:
1435:as each of the
1408:
1405:
1404:
1372:
1368:
1366:
1363:
1362:
1330:
1326:
1324:
1321:
1320:
1303:
1299:
1297:
1294:
1293:
1277:
1274:
1273:
1247:
1243:
1241:
1238:
1237:
1205:
1201:
1199:
1196:
1195:
1179:
1176:
1175:
1159:
1156:
1155:
1133:
1130:
1129:
1113:
1110:
1109:
1093:
1090:
1089:
1073:
1070:
1069:
1032:
1029:
1028:
935:
932:
931:
912:
909:
908:
892:
889:
888:
872:
869:
868:
852:
849:
848:
832:
829:
828:
812:
809:
808:
765:
762:
761:
744:
740:
738:
735:
734:
718:
715:
714:
698:
695:
694:
678:
675:
674:
658:
655:
654:
638:
635:
634:
614:
613:
602:
584:
583:
578:
575:
574:
558:
555:
554:
535:
530:
527:
526:
510:
507:
506:
490:
487:
486:
469:
468:
457:
436:
435:
430:
427:
426:
401:
398:
397:
376:
372:
370:
367:
366:
347:
343:
341:
338:
337:
318:
314:
312:
309:
308:
289:
285:
283:
280:
279:
254:
251:
250:
228:
225:
224:
208:
205:
204:
203:in each of the
188:
185:
184:
168:
165:
164:
148:
142:
138:
133:
127:
121:
118:
117:
100:
96:
94:
91:
90:
74:
71:
70:
67:
59:Chazelle (1983)
47:range searching
26:binary searches
12:
11:
5:
4664:
4654:
4653:
4648:
4643:
4628:
4627:
4615:
4604:Willard, D. E.
4600:
4590:(2): 161–172,
4579:
4561:(1): 215–241,
4551:Mehlhorn, Kurt
4547:
4522:
4508:
4477:
4462:
4448:
4420:
4410:(1): 317–340,
4385:
4371:
4348:
4328:(2): 269–284,
4307:
4264:
4221:
4201:(4): 509–517,
4180:
4161:
4133:
4119:
4071:
4069:
4066:
4022:point location
3937:
3934:
3906:
3905:
3893:
3878:
3813:
3810:
3756:in which each
3754:directed graph
3745:
3742:
3727:
3723:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3681:
3678:
3674:
3670:
3667:
3662:
3659:
3654:
3649:
3646:
3641:
3638:
3634:
3629:
3623:
3619:
3614:
3610:
3607:
3603:
3597:
3593:
3588:
3584:
3564:
3561:
3558:
3554:
3548:
3545:
3542:
3538:
3533:
3525:
3521:
3517:
3512:
3509:
3506:
3502:
3496:
3493:
3490:
3486:
3481:
3475:
3472:
3467:
3463:
3457:
3454:
3451:
3447:
3442:
3436:
3433:
3428:
3424:
3418:
3414:
3409:
3386:
3382:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3318:
3315:
3312:
3292:
3270:
3267:
3264:
3260:
3239:
3217:
3214:
3211:
3207:
3184:
3180:
3159:
3137:
3134:
3131:
3127:
3104:
3100:
3079:
3059:
3056:
3053:
3031:
3027:
3006:
2984:
2980:
2959:
2934:
2930:
2909:
2889:
2886:
2883:
2880:
2877:
2872:
2868:
2845:
2841:
2820:
2800:
2778:
2774:
2753:
2733:
2730:
2727:
2724:
2721:
2716:
2712:
2702:should return
2689:
2685:
2664:
2642:
2638:
2617:
2595:
2591:
2570:
2548:
2544:
2523:
2501:
2497:
2476:
2456:
2453:
2450:
2445:
2441:
2431:should return
2418:
2414:
2393:
2371:
2367:
2346:
2324:
2320:
2299:
2277:
2273:
2252:
2228:
2225:
2222:
2219:
2216:
2211:
2207:
2197:should return
2184:
2180:
2159:
2133:
2129:
2108:
2088:
2085:
2082:
2071:
2070:
2037:
2033:
2022:
1985:
1981:
1970:
1933:
1929:
1918:
1873:
1869:
1843:
1840:
1837:
1833:
1812:
1790:
1786:
1765:
1745:
1723:
1720:
1717:
1713:
1690:
1686:
1663:
1659:
1636:
1632:
1622:, is equal to
1609:
1605:
1582:
1578:
1557:
1554:
1551:
1548:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1484:
1464:
1444:
1424:
1421:
1418:
1415:
1412:
1392:
1389:
1386:
1383:
1380:
1375:
1371:
1350:
1347:
1344:
1341:
1338:
1333:
1329:
1306:
1302:
1281:
1261:
1258:
1255:
1250:
1246:
1225:
1222:
1219:
1216:
1213:
1208:
1204:
1183:
1163:
1143:
1140:
1137:
1117:
1097:
1077:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1025:
1024:
1023:
1022:
1001:
939:
916:
896:
876:
856:
836:
816:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
747:
743:
722:
702:
682:
662:
642:
617:
612:
609:
605:
601:
598:
595:
592:
587:
582:
562:
542:
538:
534:
514:
494:
472:
467:
464:
460:
456:
453:
450:
447:
444:
439:
434:
414:
411:
408:
405:
394:
393:
379:
375:
364:
350:
346:
335:
321:
317:
306:
292:
288:
264:
261:
258:
238:
235:
232:
212:
192:
172:
151:
145:
141:
136:
130:
126:
103:
99:
89:ordered lists
78:
66:
63:
55:Willard (1978)
9:
6:
4:
3:
2:
4663:
4652:
4649:
4647:
4644:
4642:
4639:
4638:
4636:
4623:
4622:
4616:
4611:
4610:
4605:
4601:
4597:
4593:
4589:
4585:
4580:
4576:
4572:
4568:
4564:
4560:
4556:
4552:
4548:
4544:
4540:
4536:
4532:
4528:
4523:
4519:
4515:
4511:
4505:
4501:
4497:
4492:
4491:10.1.1.39.697
4487:
4483:
4478:
4470:
4469:
4463:
4459:
4455:
4451:
4445:
4441:
4437:
4433:
4426:
4421:
4417:
4413:
4409:
4405:
4398:
4394:
4390:
4386:
4382:
4378:
4374:
4368:
4363:
4358:
4354:
4349:
4345:
4341:
4336:
4331:
4327:
4323:
4316:
4312:
4308:
4304:
4300:
4296:
4292:
4288:
4284:
4277:
4273:
4269:
4265:
4261:
4257:
4253:
4249:
4245:
4241:
4234:
4230:
4226:
4222:
4218:
4214:
4209:
4204:
4200:
4196:
4189:
4185:
4181:
4177:
4170:
4166:
4162:
4158:on 2004-10-20
4154:
4150:
4143:
4139:
4138:Suri, Subhash
4134:
4130:
4126:
4122:
4116:
4112:
4108:
4103:
4098:
4094:
4093:
4085:
4081:
4077:
4073:
4072:
4065:
4063:
4059:
4055:
4051:
4047:
4043:
4038:
4036:
4032:
4027:
4023:
4018:
4016:
4012:
4008:
4004:
4001: +
4000:
3996:
3991:
3986:
3982:
3978:
3977:convex layers
3974:
3970:
3966:
3962:
3961:
3955:
3951:
3942:
3933:
3931:
3927:
3924: +
3923:
3919:
3915:
3911:
3903:
3899:
3894:
3891:
3887:
3883:
3879:
3876:
3873:technique of
3872:
3867:
3866:
3865:
3863:
3858:
3854:
3849:
3847:
3843:
3839:
3835:
3831:
3825:
3821:
3819:
3809:
3807:
3803:
3797:
3795:
3791:
3787:
3783:
3779:
3774:
3771:
3767:
3763:
3759:
3755:
3751:
3750:catalog graph
3741:
3725:
3721:
3700:
3694:
3688:
3685:
3682:
3679:
3676:
3672:
3668:
3665:
3660:
3657:
3652:
3647:
3644:
3639:
3636:
3632:
3621:
3617:
3608:
3605:
3595:
3591:
3582:
3562:
3559:
3556:
3546:
3543:
3540:
3536:
3523:
3519:
3515:
3510:
3507:
3504:
3494:
3491:
3488:
3484:
3473:
3470:
3465:
3455:
3452:
3449:
3445:
3434:
3431:
3426:
3416:
3412:
3384:
3380:
3370:
3354:
3351:
3348:
3345:
3342:
3336:
3316:
3313:
3310:
3290:
3268:
3265:
3262:
3258:
3237:
3215:
3212:
3209:
3205:
3182:
3178:
3157:
3135:
3132:
3129:
3125:
3102:
3098:
3077:
3057:
3054:
3051:
3029:
3025:
3004:
2982:
2978:
2957:
2948:
2932:
2928:
2907:
2887:
2884:
2878:
2870:
2866:
2843:
2839:
2818:
2798:
2776:
2772:
2751:
2731:
2728:
2722:
2714:
2710:
2687:
2683:
2662:
2640:
2636:
2615:
2593:
2589:
2568:
2546:
2542:
2521:
2499:
2495:
2474:
2451:
2443:
2439:
2416:
2412:
2391:
2369:
2365:
2344:
2322:
2318:
2297:
2275:
2271:
2250:
2242:
2239:. The "5" in
2226:
2223:
2217:
2209:
2205:
2182:
2178:
2157:
2149:
2131:
2127:
2106:
2086:
2083:
2080:
2069:
2065:
2061:
2057:
2053:
2035:
2031:
2023:
2021:
2017:
2013:
2009:
2005:
2001:
1983:
1979:
1971:
1969:
1965:
1961:
1957:
1953:
1949:
1931:
1927:
1919:
1917:
1913:
1909:
1905:
1901:
1897:
1893:
1889:
1871:
1867:
1859:
1858:
1857:
1841:
1838:
1835:
1831:
1810:
1788:
1784:
1763:
1743:
1721:
1718:
1715:
1711:
1688:
1684:
1661:
1657:
1634:
1630:
1607:
1603:
1580:
1576:
1552:
1546:
1523:
1520:
1517:
1514:
1511:
1505:
1496:
1482:
1462:
1442:
1419:
1416:
1410:
1390:
1387:
1381:
1373:
1369:
1348:
1345:
1339:
1331:
1327:
1304:
1300:
1279:
1256:
1248:
1244:
1223:
1220:
1214:
1206:
1202:
1181:
1161:
1141:
1138:
1135:
1115:
1095:
1075:
1052:
1049:
1046:
1043:
1040:
1034:
1021:
1017:
1013:
1009:
1005:
1002:
999:
995:
991:
987:
983:
979:
976:
975:
973:
969:
965:
961:
957:
953:
937:
930:
929:
928:
914:
894:
874:
854:
834:
814:
791:
788:
785:
782:
779:
776:
773:
767:
745:
741:
720:
700:
680:
660:
640:
631:
607:
603:
599:
593:
590:
580:
560:
540:
536:
532:
512:
492:
462:
458:
454:
448:
445:
442:
432:
409:
403:
377:
373:
365:
348:
344:
336:
319:
315:
307:
290:
286:
278:
277:
276:
262:
259:
256:
236:
233:
230:
210:
190:
170:
143:
139:
128:
124:
101:
97:
76:
62:
60:
56:
52:
51:Lueker (1978)
48:
44:
40:
36:
32:
27:
23:
19:
4620:
4608:
4587:
4583:
4558:
4555:Algorithmica
4554:
4526:
4481:
4467:
4431:
4407:
4403:
4352:
4325:
4321:
4286:
4283:Algorithmica
4282:
4243:
4240:Algorithmica
4239:
4198:
4194:
4175:
4153:the original
4148:
4091:
4039:
4034:
4030:
4019:
4010:
4006:
4002:
3998:
3994:
3972:
3964:
3957:
3950:range search
3947:
3936:Applications
3929:
3925:
3921:
3917:
3913:
3909:
3907:
3901:
3897:
3889:
3885:
3875:Dietz (1982)
3861:
3856:
3852:
3850:
3845:
3841:
3833:
3829:
3826:
3822:
3817:
3815:
3805:
3801:
3798:
3793:
3789:
3785:
3781:
3777:
3775:
3769:
3765:
3749:
3747:
3371:
2949:
2240:
2147:
2072:
2067:
2063:
2059:
2055:
2051:
2019:
2015:
2011:
2007:
2003:
1999:
1967:
1963:
1959:
1955:
1951:
1947:
1915:
1911:
1907:
1903:
1899:
1895:
1891:
1887:
1539:, and space
1497:
1026:
1019:
1015:
1011:
1007:
1003:
997:
993:
989:
985:
981:
977:
971:
967:
963:
959:
955:
951:
632:
395:
334:= 23, 25, 26
68:
21:
15:
3985:convex hull
3958:half-plane
4635:Categories
4393:Stolfi, J.
4068:References
3969:half-plane
4486:CiteSeerX
4330:CiteSeerX
4203:CiteSeerX
4102:0904.4670
3677:≤
3669:⋯
3609:∑
3583:∑
3560:⋯
3508:⋯
3352:
1521:
1455:items in
1050:
594:
449:
125:∑
37:in 1986 (
4606:(1978),
4543:14970942
4518:15363397
4395:(1986),
4381:24008786
4303:11232235
4274:(1986),
4260:12745042
4231:(1986),
4186:(1985),
4167:(1983),
31:Chazelle
4575:7721690
4458:1033287
4129:2590335
3838:B-trees
65:Example
4573:
4541:
4516:
4506:
4488:
4456:
4446:
4379:
4369:
4332:
4301:
4258:
4205:
4127:
4117:
3758:vertex
1361:, and
887:, and
807:where
35:Guibas
4571:S2CID
4539:S2CID
4514:S2CID
4472:(PDF)
4454:S2CID
4428:(PDF)
4400:(PDF)
4377:S2CID
4318:(PDF)
4299:S2CID
4279:(PDF)
4256:S2CID
4236:(PDF)
4191:(PDF)
4172:(PDF)
4156:(PDF)
4145:(PDF)
4125:S2CID
4097:arXiv
4087:(PDF)
4504:ISBN
4444:ISBN
4367:ISBN
4115:ISBN
4044:and
3762:path
3752:, a
3055:>
249:and
53:and
33:and
4592:doi
4563:doi
4531:doi
4496:doi
4436:doi
4412:doi
4357:doi
4340:doi
4291:doi
4248:doi
4213:doi
4107:doi
4052:in
3932:).
3816:In
3349:log
3303:to
3250:in
3170:in
3090:in
3017:in
2970:in
2858:is
2831:in
2764:in
2675:in
2581:in
2534:in
2404:in
2310:in
2263:in
2170:in
2119:in
1823:in
1776:in
1518:log
1319:),
1174:in
1088:in
1047:log
693:of
591:log
446:log
16:In
4637::
4588:19
4586:,
4569:,
4557:,
4537:,
4512:,
4502:,
4494:,
4452:,
4442:,
4430:,
4408:15
4406:,
4402:,
4375:,
4365:,
4338:,
4326:68
4324:,
4320:,
4297:,
4285:,
4281:,
4270:;
4254:,
4242:,
4238:,
4227:;
4211:,
4199:31
4197:,
4193:,
4174:,
4147:,
4123:,
4113:,
4105:,
4089:,
4064:.
4056:.
3800:1/
2888:79
2732:62
2241:64
2227:64
2148:64
2087:50
2068:81
2066:,
2064:79
2062:,
2060:46
2058:,
2056:35
2054:,
2052:11
2050:=
2020:79
2018:,
2016:66
2014:,
2012:62
2010:,
2008:44
2006:,
2004:35
2002:,
2000:13
1998:=
1968:79
1966:,
1964:62
1962:,
1960:35
1958:,
1956:26
1954:,
1952:25
1950:,
1948:23
1946:=
1916:93
1914:,
1912:80
1910:,
1908:79
1906:,
1904:65
1902:,
1900:64
1898:,
1896:35
1894:,
1892:25
1890:,
1888:24
1886:=
1391:79
1349:62
1236:,
1224:64
1142:50
1020:93
1018:,
1016:81
1014:,
1012:80
1010:,
1008:79
1006:,
1004:66
998:65
996:,
994:64
992:,
990:62
988:,
986:46
984:,
982:44
980:,
978:35
974:,
972:26
970:,
968:25
966:,
964:24
962:,
960:23
958:,
956:13
954:,
952:11
950:=
867:,
847:,
630:.
275:,
263:17
41:;
20:,
4626:.
4614:.
4599:.
4594::
4578:.
4565::
4559:5
4546:.
4533::
4521:.
4498::
4476:.
4461:.
4438::
4419:.
4414::
4384:.
4359::
4347:.
4342::
4306:.
4293::
4287:1
4263:.
4250::
4244:1
4220:.
4215::
4179:.
4160:.
4132:.
4109::
4099::
4035:n
4031:n
4011:n
4007:n
4003:h
3999:n
3995:n
3973:h
3965:n
3930:n
3926:k
3922:n
3918:k
3914:k
3910:n
3902:x
3898:x
3890:x
3886:x
3862:x
3857:x
3853:x
3846:d
3842:d
3834:d
3830:d
3806:r
3802:r
3794:d
3790:d
3786:d
3782:d
3778:d
3770:q
3766:q
3726:i
3722:L
3701:,
3698:)
3695:n
3692:(
3689:O
3686:=
3683:n
3680:2
3673:)
3666:+
3661:4
3658:1
3653:+
3648:2
3645:1
3640:+
3637:1
3633:(
3628:|
3622:i
3618:L
3613:|
3606:=
3602:|
3596:i
3592:M
3587:|
3563:,
3557:+
3553:|
3547:j
3544:+
3541:i
3537:L
3532:|
3524:j
3520:2
3516:1
3511:+
3505:+
3501:|
3495:2
3492:+
3489:i
3485:L
3480:|
3474:4
3471:1
3466:+
3462:|
3456:1
3453:+
3450:i
3446:L
3441:|
3435:2
3432:1
3427:+
3423:|
3417:i
3413:L
3408:|
3385:i
3381:M
3358:)
3355:n
3346:+
3343:k
3340:(
3337:O
3317:1
3314:+
3311:i
3291:i
3269:1
3266:+
3263:i
3259:M
3238:q
3216:1
3213:+
3210:i
3206:M
3183:i
3179:M
3158:q
3136:1
3133:+
3130:i
3126:M
3103:i
3099:M
3078:q
3058:1
3052:i
3030:1
3026:L
3005:q
2983:1
2979:M
2958:q
2933:1
2929:M
2908:q
2885:=
2882:]
2879:3
2876:[
2871:4
2867:L
2844:4
2840:L
2819:q
2799:q
2777:4
2773:M
2752:q
2729:=
2726:]
2723:2
2720:[
2715:3
2711:L
2688:3
2684:L
2663:q
2641:3
2637:M
2616:q
2594:3
2590:M
2569:q
2547:3
2543:M
2522:q
2500:2
2496:L
2475:q
2455:]
2452:3
2449:[
2444:2
2440:L
2417:2
2413:L
2392:q
2370:2
2366:M
2345:q
2323:2
2319:M
2298:q
2276:2
2272:M
2251:q
2224:=
2221:]
2218:1
2215:[
2210:1
2206:L
2183:1
2179:L
2158:q
2132:1
2128:M
2107:q
2084:=
2081:q
2036:4
2032:M
1984:3
1980:M
1932:2
1928:M
1872:1
1868:M
1842:1
1839:+
1836:i
1832:M
1811:x
1789:i
1785:L
1764:x
1744:x
1722:1
1719:+
1716:i
1712:M
1689:i
1685:L
1662:i
1658:M
1635:k
1631:L
1608:k
1604:M
1581:i
1577:M
1556:)
1553:n
1550:(
1547:O
1527:)
1524:n
1515:+
1512:k
1509:(
1506:O
1483:k
1463:L
1443:n
1423:)
1420:n
1417:k
1414:(
1411:O
1388:=
1385:]
1382:3
1379:[
1374:4
1370:L
1346:=
1343:]
1340:2
1337:[
1332:3
1328:L
1305:2
1301:L
1280:q
1260:]
1257:3
1254:[
1249:2
1245:L
1221:=
1218:]
1215:1
1212:[
1207:1
1203:L
1182:L
1162:q
1139:=
1136:q
1116:x
1096:L
1076:q
1056:)
1053:n
1044:+
1041:k
1038:(
1035:O
1000:,
938:L
915:x
895:d
875:c
855:b
835:a
815:x
795:]
792:d
789:,
786:c
783:,
780:b
777:,
774:a
771:[
768:x
746:i
742:L
721:x
701:L
681:x
661:L
641:k
616:)
611:)
608:k
604:/
600:n
597:(
586:(
581:O
561:k
541:k
537:/
533:n
513:k
493:k
471:)
466:)
463:k
459:/
455:n
452:(
443:k
438:(
433:O
413:)
410:n
407:(
404:O
378:4
374:L
349:3
345:L
320:2
316:L
291:1
287:L
260:=
257:n
237:4
234:=
231:k
211:k
191:q
171:n
150:|
144:i
140:L
135:|
129:i
102:i
98:L
77:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
