209:
17:
1305:. Colored range searching is also used for and motivated by searching through categorical data. For example, determining the rows in a database of bank accounts which represent people whose age is between 25 and 40 and who have between $ 10000 and $ 20000 might be an orthogonal range reporting problem where age and money are two dimensions.
1190:
attributes. If the categories are considered as colors of points in geometric space, then a query is for how many colors appear in a particular range. Prosenjit Gupta and others described a data structure in 1995 which solved 2D orthogonal colored range counting in
1034:
range searching, insertions and deletions of points are allowed. In the incremental version of the problem, only insertions are allowed, whereas the decremental version only allows deletions. For the orthogonal case,
87:
There are several variations of the problem, and different data structures may be necessary for different variations. In order to obtain an efficient solution, several aspects of the problem need to be specified:
1356:
Advances in
Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke
695:
806:
386:
914:
212:
A 2D orthogonal range query. In this case, a range reporting query would return the two circled points, a range counting query would return 2, and an emptiness query would return false.
1135:
961:
1241:
551:
1008:
489:
852:
438:
1283:
1176:
1079:
604:
1018:, the query is called three-sided. If two of the bounds are infinity, the query is two-sided, and if none of the bounds are infinity, then the query is four-sided.
742:
633:
323:
1634:
Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1995). "Further results on generalized intersection searching problems: Counting, reporting, and dynamization".
282:
258:
238:
1538:
119:
Range types: The query ranges also need to be drawn from a predetermined set. Some well-studied sets of ranges, and the names of the respective problems are
1536:
JaJa, Joseph; Mortensen, Christian; Shi, Qingmin (2005). "Space-efficient and fast algorithms for multidimensional dominance reporting and counting".
1557:
709:
638:
747:
1591:
328:
260:
dimensions, and the query consists of intervals in each of those dimensions. Thus, the query consists of a multi-dimensional
1703:
1562:
48:
is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of
1040:
1750:
1694:
1416:
1370:
285:
150:. Sometimes, only the number of objects that intersect the range is required. In this case, the problem is called
857:
142:
Query types: If the list of all objects that intersect the query range must be reported, the problem is called
68:
1084:
921:
1194:
1178:
query time, but it is unknown whether general dynamic range searching can be done with that query time.
502:
181:, and it is required to report the semigroup sum of the weights of the points that intersect the range.
966:
443:
1499:
1467:
1425:
1379:
813:
395:
1513:
712:, also using compressed range trees in the word RAM model of computation, are one of the following:
1755:
1246:
194:
Offline range searching: Both the set of objects and the whole set of queries are known in advance.
1140:
1046:
1508:
1298:
1294:
698:
574:
261:
120:
64:
1497:(1988). "A functional approach to data structures and its use in multidimensional searching".
1712:
1636:
1359:, Contemporary Mathematics, vol. 223, American Mathematical Society Press, pp. 1–56
128:
72:
1187:
704:
As of 2015, the best results (in low dimensions (2D, 3D, 4D)) for range reporting found by
564:
496:
191:
is known in advance. In dynamic setting objects may be inserted or deleted between queries.
1658:
718:
609:
299:
8:
1137:
query time. Both incremental and decremental versions of the problem can be solved with
1729:
1616:
1567:
1444:
1398:
267:
243:
223:
1297:, range searching, and orthogonal range searching in particular, has applications for
1690:
1683:
1339:
389:
1733:
1707:
1402:
1721:
1653:
1645:
1620:
1608:
1518:
1494:
1476:
1448:
1434:
1388:
1351:
1347:
635:
space for range counting. Joseph JaJa and others later improved this query time to
568:
97:
25:
1553:
1343:
1039:
and Stefan Näher created a data structure for dynamic range searching which uses
705:
557:
143:
101:
293:
162:
reports whether there is at least one object that intersects the range. In the
60:
1744:
1678:
1587:
1036:
1649:
1599:
1186:
The problem of colored range counting considers the case where points have
1031:
184:
105:
1725:
1439:
1420:
1393:
1374:
187:
range searching vs. static range searching: In the static setting the set
1462:
1319:
492:
208:
167:
16:
1612:
1314:
1676:
1375:"Multidimensional binary search trees used for associative searching"
170:
109:
53:
1522:
1480:
1302:
1015:
561:
289:
76:
49:
1572:
124:
113:
116:.... The simplest and most studied objects to search are points.
136:
132:
1560:(2011). "Orthogonal range searching on the RAM, revisited".
1465:(1985). "New data structures for orthogonal range queries".
697:
for range counting, which matches a lower bound and is thus
690:{\displaystyle O\left({\dfrac {\log n}{\log \log n}}\right)}
801:{\displaystyle O(\log ^{\epsilon }n+k\log ^{\epsilon }n)}
381:{\displaystyle O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}}
177:,+) is specified, each point is assigned a weight from
1539:
International
Symposium on Algorithms and Computation
1249:
1197:
1143:
1087:
1049:
969:
924:
860:
816:
750:
721:
650:
641:
612:
577:
505:
446:
398:
331:
302:
270:
246:
226:
67:. Applications of the problem arise in areas such as
36:
of objects, in order to determine which objects from
1682:
1552:
1277:
1235:
1170:
1129:
1073:
1002:
955:
908:
846:
800:
736:
689:
627:
598:
560:model, further improvements have been made in the
545:
483:
432:
380:
317:
276:
252:
232:
1633:
1742:
1535:
1014:In the orthogonal case, if one of the bounds is
1338:
1586:
1344:"Geometric Range Searching and Its Relatives"
556:While the above results were achieved in the
373:
337:
203:
909:{\displaystyle O(\log \log n+k\log \log n)}
92:Object types: Algorithms depend on whether
1181:
1021:
40:intersect with a query object, called the
1689:(2nd ed.), Berlin: Springer-Verlag,
1657:
1580:
1571:
1512:
1487:
1438:
1392:
63:that solve it are a fundamental topic of
1702:
1493:
1455:
1409:
1363:
1332:
1026:While in static range searching the set
388:query time. Bentley also proposed using
207:
15:
1461:
1415:
1369:
216:In orthogonal range searching, the set
1743:
1627:
1130:{\displaystyle O(\log n\log \log n+k)}
956:{\displaystyle O(n\log ^{\epsilon }n)}
1546:
1529:
1421:"Multidimensional divide-and-conquer"
571:used compress range trees to achieve
495:used downpointers, a special case of
32:problem consists of processing a set
499:to reduce the query time further to
59:The range searching problem and the
1563:Symposium on Computational Geometry
1293:In addition to being considered in
13:
1677:de Berg, Mark; van Kreveld, Marc;
1670:
1236:{\displaystyle O(n^{2}\log ^{2}n)}
198:
14:
1767:
546:{\displaystyle O(\log ^{d-1}n+k)}
1003:{\displaystyle O(\log \log n+k)}
567:in low dimensions (2D, 3D, 4D).
484:{\displaystyle O(n\log ^{d-1}n)}
69:geographical information systems
1681:; Schwarzkopf, Otfried (2000),
1288:
847:{\displaystyle O(n\log \log n)}
433:{\displaystyle O(\log ^{d}n+k)}
392:, which improved query time to
1659:11858/00-001M-0000-0014-B721-F
1592:"Dynamic fractional cascading"
1272:
1253:
1230:
1201:
1165:
1147:
1124:
1091:
1068:
1053:
997:
973:
950:
928:
903:
864:
841:
820:
795:
754:
731:
725:
622:
616:
593:
581:
540:
509:
478:
450:
427:
402:
312:
306:
123:(orthogonal range searching),
1:
1325:
1278:{\displaystyle O(\log ^{2}n)}
82:
1041:dynamic fractional cascading
154:, and the query is called a
146:, and the query is called a
7:
1708:"Geometric range searching"
1354:; Pollack, Richard (eds.),
1308:
1171:{\displaystyle O(\log n+k)}
10:
1772:
1074:{\displaystyle O(n\log n)}
204:Orthogonal range searching
1751:Geometric data structures
1500:SIAM Journal on Computing
1468:SIAM Journal on Computing
1426:Communications of the ACM
1380:Communications of the ACM
599:{\displaystyle O(\log n)}
264:. With an output size of
1590:; Näher, Stefan (1990).
20:Simplex range searching.
1342:; Erickson, J. (1999),
1182:Colored range searching
1022:Dynamic range searching
440:but increased space to
121:axis-aligned rectangles
1685:Computational Geometry
1650:10.1006/jagm.1995.1038
1295:computational geometry
1279:
1237:
1172:
1131:
1075:
1004:
957:
910:
848:
802:
738:
699:asymptotically optimal
691:
629:
600:
547:
485:
434:
382:
319:
278:
262:axis-aligned rectangle
254:
234:
213:
65:computational geometry
21:
1726:10.1145/197405.197408
1713:ACM Computing Surveys
1637:Journal of Algorithms
1440:10.1145/358841.358850
1394:10.1145/361002.361007
1280:
1238:
1173:
1132:
1076:
1030:is known in advance,
1005:
958:
911:
849:
803:
739:
708:, Kasper Larsen, and
692:
630:
601:
548:
486:
435:
383:
320:
279:
255:
235:
211:
73:computer-aided design
19:
1247:
1195:
1141:
1085:
1047:
967:
922:
858:
814:
748:
737:{\displaystyle O(n)}
719:
639:
628:{\displaystyle O(n)}
610:
575:
565:model of computation
503:
497:fractional cascading
444:
396:
329:
318:{\displaystyle O(n)}
300:
268:
244:
224:
1613:10.1007/BF01840386
1556:; Larsen, Kasper;
1275:
1233:
1168:
1127:
1071:
1000:
953:
906:
844:
798:
734:
687:
681:
625:
596:
543:
481:
430:
378:
315:
274:
250:
230:
214:
44:. For example, if
22:
1495:Chazelle, Bernard
1348:Chazelle, Bernard
680:
361:
277:{\displaystyle k}
253:{\displaystyle d}
233:{\displaystyle n}
164:semigroup version
1763:
1736:
1699:
1688:
1664:
1663:
1661:
1631:
1625:
1624:
1596:
1584:
1578:
1577:
1575:
1550:
1544:
1543:
1533:
1527:
1526:
1516:
1491:
1485:
1484:
1459:
1453:
1452:
1442:
1413:
1407:
1406:
1396:
1367:
1361:
1360:
1336:
1284:
1282:
1281:
1276:
1265:
1264:
1242:
1240:
1239:
1234:
1223:
1222:
1213:
1212:
1177:
1175:
1174:
1169:
1136:
1134:
1133:
1128:
1080:
1078:
1077:
1072:
1009:
1007:
1006:
1001:
962:
960:
959:
954:
943:
942:
915:
913:
912:
907:
853:
851:
850:
845:
807:
805:
804:
799:
788:
787:
766:
765:
743:
741:
740:
735:
696:
694:
693:
688:
686:
682:
679:
662:
651:
634:
632:
631:
626:
605:
603:
602:
597:
569:Bernard Chazelle
552:
550:
549:
544:
527:
526:
490:
488:
487:
482:
471:
470:
439:
437:
436:
431:
414:
413:
387:
385:
384:
379:
377:
376:
364:
363:
362:
354:
341:
340:
324:
322:
321:
316:
283:
281:
280:
275:
259:
257:
256:
251:
239:
237:
236:
231:
26:computer science
1771:
1770:
1766:
1765:
1764:
1762:
1761:
1760:
1756:Database theory
1741:
1740:
1697:
1673:
1671:Further reading
1668:
1667:
1632:
1628:
1594:
1585:
1581:
1558:Pătrașcu, Mihai
1551:
1547:
1534:
1530:
1523:10.1137/0217026
1514:10.1.1.133.9153
1492:
1488:
1481:10.1137/0214019
1460:
1456:
1414:
1410:
1368:
1364:
1337:
1333:
1328:
1311:
1291:
1260:
1256:
1248:
1245:
1244:
1218:
1214:
1208:
1204:
1196:
1193:
1192:
1184:
1142:
1139:
1138:
1086:
1083:
1082:
1048:
1045:
1044:
1024:
968:
965:
964:
938:
934:
923:
920:
919:
859:
856:
855:
815:
812:
811:
783:
779:
761:
757:
749:
746:
745:
720:
717:
716:
706:Timothy M. Chan
663:
652:
649:
645:
640:
637:
636:
611:
608:
607:
606:query time and
576:
573:
572:
558:pointer machine
516:
512:
504:
501:
500:
460:
456:
445:
442:
441:
409:
405:
397:
394:
393:
372:
371:
353:
346:
342:
336:
335:
330:
327:
326:
301:
298:
297:
292:to achieve (in
269:
266:
265:
245:
242:
241:
225:
222:
221:
206:
201:
199:Data structures
160:emptiness query
148:reporting query
144:range reporting
85:
61:data structures
30:range searching
12:
11:
5:
1769:
1759:
1758:
1753:
1739:
1738:
1720:(4): 421–461,
1704:Matoušek, Jiří
1700:
1695:
1679:Overmars, Mark
1672:
1669:
1666:
1665:
1644:(2): 282–317.
1626:
1607:(2): 215–241.
1588:Mehlhorn, Kurt
1579:
1545:
1528:
1507:(3): 427–462.
1486:
1475:(1): 232–253.
1454:
1433:(4): 214–229.
1408:
1387:(9): 509–517.
1362:
1352:Goodman, Jacob
1340:Agarwal, P. K.
1330:
1329:
1327:
1324:
1323:
1322:
1317:
1310:
1307:
1290:
1287:
1274:
1271:
1268:
1263:
1259:
1255:
1252:
1232:
1229:
1226:
1221:
1217:
1211:
1207:
1203:
1200:
1183:
1180:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1023:
1020:
1012:
1011:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
952:
949:
946:
941:
937:
933:
930:
927:
917:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
843:
840:
837:
834:
831:
828:
825:
822:
819:
809:
797:
794:
791:
786:
782:
778:
775:
772:
769:
764:
760:
756:
753:
733:
730:
727:
724:
710:Mihai Pătrașcu
685:
678:
675:
672:
669:
666:
661:
658:
655:
648:
644:
624:
621:
618:
615:
595:
592:
589:
586:
583:
580:
542:
539:
536:
533:
530:
525:
522:
519:
515:
511:
508:
480:
477:
474:
469:
466:
463:
459:
455:
452:
449:
429:
426:
423:
420:
417:
412:
408:
404:
401:
375:
370:
367:
360:
357:
352:
349:
345:
339:
334:
314:
311:
308:
305:
294:Big O notation
273:
249:
229:
205:
202:
200:
197:
196:
195:
192:
182:
156:counting query
152:range counting
140:
117:
84:
81:
9:
6:
4:
3:
2:
1768:
1757:
1754:
1752:
1749:
1748:
1746:
1735:
1731:
1727:
1723:
1719:
1715:
1714:
1709:
1705:
1701:
1698:
1696:3-540-65620-0
1692:
1687:
1686:
1680:
1675:
1674:
1660:
1655:
1651:
1647:
1643:
1639:
1638:
1630:
1622:
1618:
1614:
1610:
1606:
1602:
1601:
1593:
1589:
1583:
1574:
1569:
1565:
1564:
1559:
1555:
1554:Chan, Timothy
1549:
1541:
1540:
1532:
1524:
1520:
1515:
1510:
1506:
1502:
1501:
1496:
1490:
1482:
1478:
1474:
1470:
1469:
1464:
1458:
1450:
1446:
1441:
1436:
1432:
1428:
1427:
1422:
1418:
1412:
1404:
1400:
1395:
1390:
1386:
1382:
1381:
1376:
1372:
1366:
1358:
1353:
1349:
1345:
1341:
1335:
1331:
1321:
1318:
1316:
1313:
1312:
1306:
1304:
1300:
1299:range queries
1296:
1286:
1269:
1266:
1261:
1257:
1250:
1227:
1224:
1219:
1215:
1209:
1205:
1198:
1189:
1179:
1162:
1159:
1156:
1153:
1150:
1144:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1088:
1065:
1062:
1059:
1056:
1050:
1042:
1038:
1037:Kurt Mehlhorn
1033:
1029:
1019:
1017:
994:
991:
988:
985:
982:
979:
976:
970:
947:
944:
939:
935:
931:
925:
918:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
861:
838:
835:
832:
829:
826:
823:
817:
810:
792:
789:
784:
780:
776:
773:
770:
767:
762:
758:
751:
728:
722:
715:
714:
713:
711:
707:
702:
700:
683:
676:
673:
670:
667:
664:
659:
656:
653:
646:
642:
619:
613:
590:
587:
584:
578:
570:
566:
563:
559:
554:
537:
534:
531:
528:
523:
520:
517:
513:
506:
498:
494:
475:
472:
467:
464:
461:
457:
453:
447:
424:
421:
418:
415:
410:
406:
399:
391:
368:
365:
358:
355:
350:
347:
343:
332:
309:
303:
295:
291:
287:
271:
263:
247:
227:
219:
210:
193:
190:
186:
183:
180:
176:
172:
169:
165:
161:
157:
153:
149:
145:
141:
138:
134:
130:
126:
122:
118:
115:
111:
107:
106:line segments
103:
99:
95:
91:
90:
89:
80:
78:
74:
70:
66:
62:
57:
55:
51:
47:
43:
39:
35:
31:
27:
18:
1717:
1711:
1684:
1641:
1635:
1629:
1604:
1600:Algorithmica
1598:
1582:
1561:
1548:
1537:
1531:
1504:
1498:
1489:
1472:
1466:
1463:Willard, Dan
1457:
1430:
1424:
1417:Bentley, Jon
1411:
1384:
1378:
1371:Bentley, Jon
1365:
1355:
1334:
1292:
1289:Applications
1285:query time.
1185:
1027:
1025:
1013:
703:
555:
220:consists of
217:
215:
188:
178:
174:
163:
159:
155:
151:
147:
96:consists of
93:
86:
58:
45:
41:
37:
33:
29:
23:
1320:Range query
1188:categorical
1043:to achieve
493:Dan Willard
390:range trees
286:Jon Bentley
168:commutative
1745:Categories
1542:: 558–568.
1326:References
1315:Range tree
1243:space and
1081:space and
1010:query time
916:query time
808:query time
325:space and
240:points in
129:halfspaces
83:Variations
75:(CAD) and
54:longitudes
1573:1103.5510
1509:CiteSeerX
1303:databases
1267:
1225:
1154:
1113:
1107:
1098:
1063:
986:
980:
945:
940:ϵ
898:
892:
877:
871:
836:
830:
790:
785:ϵ
768:
763:ϵ
674:
668:
657:
588:
529:
521:−
473:
465:−
416:
351:−
171:semigroup
125:simplices
77:databases
50:latitudes
1734:17729301
1706:(1994),
1566:: 1–10.
1419:(1980).
1403:13091446
1373:(1975).
1309:See also
1016:infinity
562:word RAM
290:k-d tree
114:polygons
1621:7721690
1449:3997186
1357:College
1032:dynamic
963:space,
854:space,
744:space,
288:used a
185:Dynamic
137:circles
133:spheres
71:(GIS),
1732:
1693:
1619:
1511:
1447:
1401:
158:. The
131:, and
98:points
28:, the
1730:S2CID
1617:S2CID
1595:(PDF)
1568:arXiv
1445:S2CID
1399:S2CID
1346:, in
110:boxes
102:lines
42:range
1691:ISBN
166:, a
52:and
1722:doi
1654:hdl
1646:doi
1609:doi
1519:doi
1477:doi
1435:doi
1389:doi
1301:in
1258:log
1216:log
1151:log
1110:log
1104:log
1095:log
1060:log
983:log
977:log
936:log
895:log
889:log
874:log
868:log
833:log
827:log
781:log
759:log
671:log
665:log
654:log
585:log
553:.
514:log
458:log
407:log
24:In
1747::
1728:,
1718:26
1716:,
1710:,
1652:.
1642:19
1640:.
1615:.
1603:.
1597:.
1517:.
1505:17
1503:.
1473:14
1471:.
1443:.
1431:23
1429:.
1423:.
1397:.
1385:18
1383:.
1377:.
1350:;
701:.
491:.
296:)
284:,
127:,
112:,
108:,
104:,
100:,
79:.
56:.
1737:.
1724::
1662:.
1656::
1648::
1623:.
1611::
1605:5
1576:.
1570::
1525:.
1521::
1483:.
1479::
1451:.
1437::
1405:.
1391::
1273:)
1270:n
1262:2
1254:(
1251:O
1231:)
1228:n
1220:2
1210:2
1206:n
1202:(
1199:O
1166:)
1163:k
1160:+
1157:n
1148:(
1145:O
1125:)
1122:k
1119:+
1116:n
1101:n
1092:(
1089:O
1069:)
1066:n
1057:n
1054:(
1051:O
1028:S
998:)
995:k
992:+
989:n
974:(
971:O
951:)
948:n
932:n
929:(
926:O
904:)
901:n
886:k
883:+
880:n
865:(
862:O
842:)
839:n
824:n
821:(
818:O
796:)
793:n
777:k
774:+
771:n
755:(
752:O
732:)
729:n
726:(
723:O
684:)
677:n
660:n
647:(
643:O
623:)
620:n
617:(
614:O
594:)
591:n
582:(
579:O
541:)
538:k
535:+
532:n
524:1
518:d
510:(
507:O
479:)
476:n
468:1
462:d
454:n
451:(
448:O
428:)
425:k
422:+
419:n
411:d
403:(
400:O
374:)
369:k
366:+
359:d
356:1
348:1
344:n
338:(
333:O
313:)
310:n
307:(
304:O
272:k
248:d
228:n
218:S
189:S
179:S
175:S
173:(
139:.
135:/
94:S
46:S
38:S
34:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
