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