17:
454:
to the same grid point or to adjacent grid points. The uniform sampling of pairs in the first step of the algorithm (compared to a different method of Rabin for sampling a similar number of pairs) simplifies the proof that the expected number of distances computed by the algorithm is linear.
60:, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane was among the first geometric problems that were treated at the origins of the systematic study of the
662:
768:
is known, it can be used for the final steps of Rabin's algorithm; in these steps each grid point has a constant number of inputs rounded to it, so again the time is linear.
180:
904:
491:
222:
982:
862:
118:
425:
827:
748:
or greater, at least half of the points in expectation, from which it follows that the total expected time for filtering is linear. Once an approximate value of
947:
924:
766:
746:
726:
706:
682:
618:
598:
578:
555:
535:
511:
452:
381:
358:
338:
314:
294:
274:
54:
493:, together with a finishing step that turns this approximate distance into the exact closest distance. The filtering process repeat the following steps, until
1410:
864:
insertions and deletions and constant query time. When modified for the algebraic decision tree model, insertions and deletions would require
1288:
390:
For each input point, compute the distance to all other inputs that either round to the same grid point or to another grid point within the
1362:
1256:
1159:
124:) that would be obtained by a naive algorithm of finding distances between all pairs of points and selecting the smallest.
1405:
777:
233:
1083:
1246:
225:
1313:
462:
goes through two phases: a random iterated filtering process that approximates the closest distance to within an
906:
expected time. The complexity of the dynamic closest pair algorithm cited above is exponential in the dimension
785:
434:
The algorithm will always correctly determine the closest pair, because it maps any pair closer than distance
363:
Round the input points to a square grid of points whose size (the separation between adjacent grid points) is
998:
183:
61:
33:
792:
for efficient recalculation of the closest pair of objects each time the objects are inserted or deleted.
1023:
16th Annual
Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975
800:
for all points is known in advance and the constant-time floor function is available, then the expected
128:
949:
dimensional space was developed by Sergey
Bespamyatnikh in 1998. Points can be inserted and deleted in
626:
1234:
229:
141:
131:
1204:
867:
463:
81:
469:
236:
with this slower time bound are commonly taught as examples of these algorithm design techniques.
1338:
1209:
24th Annual
Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983
1110:
1018:
391:
1305:
189:
1135:
952:
832:
1284:
1252:
87:
397:
1371:
1322:
1230:
1212:
1176:
1168:
1092:
1044:
1026:
1385:
1334:
1190:
1106:
1381:
1330:
1186:
1102:
803:
77:
1242:
1131:
932:
926:, and therefore such an algorithm becomes less suitable for high-dimensional problems.
909:
789:
751:
731:
711:
691:
667:
603:
583:
563:
540:
520:
496:
437:
366:
343:
323:
299:
279:
259:
253:
135:
121:
39:
16:
1399:
1276:
1272:
1172:
1154:
1114:
1070:
245:
1342:
1074:
797:
57:
728:
becomes empty. Each step removes all points whose closest neighbor is at distance
73:
688:
The approximate distance found by this filtering process is the final value of
1326:
1238:
384:
387:
to collect together pairs of input points that round to the same grid point.
1097:
1078:
1304:
Golin, Mordecai; Raman, Rajeev; Schwarz, Christian; Smid, Michiel (1998).
1216:
1030:
224:
time bound, and this is optimal for this model, by a reduction from the
1376:
1357:
430:
Return the smallest of the distances computed throughout this process.
1181:
127:
It is also possible to solve the problem without randomization, in
1079:"A simple randomized sieve algorithm for the closest-pair problem"
256:
to make its analysis easier, proceeds as follows, on an input set
15:
1306:"Randomized data structures for the dynamic closest-pair problem"
1207:(1983). "Fast algorithms for the all nearest neighbors problem".
182:
time. In even more restricted models of computation, such as the
829:-space data structure was suggested that supports expected-time
340:
pairs of points uniformly at random, with replacement, and let
993:
1251:(2nd ed.). MIT Press and McGraw-Hill. pp. 957–961.
80:
whose dimension is treated as a constant for the purposes of
1049:
Algorithms and
Complexity: Recent Results and New Directions
1157:(1979). "A note on Rabin's nearest-neighbor algorithm".
684:
all points whose Moore neighborhood has no other points.
1245:(2001) . "33.4: Finding the closest pair of points".
955:
935:
929:
An algorithm for the dynamic closest-pair problem in
912:
870:
835:
806:
754:
734:
714:
694:
670:
629:
606:
586:
566:
543:
523:
499:
472:
440:
400:
369:
346:
326:
302:
282:
262:
192:
144:
90:
42:
1358:"An optimal algorithm for closest-pair maintenance"
780:for the closest-pair problem is stated as follows:
186:, the problem can be solved in the somewhat slower
1279:(2006). "5.4 Finding the closest pair of points".
976:
941:
918:
898:
856:
821:
760:
740:
720:
700:
676:
656:
612:
592:
572:
549:
529:
505:
485:
446:
419:
375:
352:
332:
308:
288:
268:
216:
174:
112:
48:
623:Round the input points to a square grid of size
134:with unlimited memory that allow the use of the
72:Randomized algorithms that solve the problem in
1021:; Hoey, Dan (1975). "Closest-point problems".
360:be the minimum distance of the selected pairs.
1054:
459:
8:
1211:. IEEE Computer Society. pp. 226–232.
1025:. IEEE Computer Society. pp. 151–162.
1375:
1180:
1096:
954:
934:
911:
881:
869:
834:
805:
753:
733:
713:
693:
669:
644:
633:
628:
605:
585:
565:
542:
522:
498:
476:
471:
439:
405:
399:
368:
345:
325:
301:
281:
261:
191:
143:
101:
89:
41:
84:. This is significantly faster than the
1010:
1363:Discrete & Computational Geometry
249:
7:
1283:. Addison-Wesley. pp. 225–231.
1126:
1124:
1065:
1063:
1047:(1976). "Probabilistic algorithms".
984:time per point (in the worst case).
20:Closest pair of points shown in red
14:
1051:. Academic Press. pp. 21–39.
240:Linear-time randomized algorithms
788:of objects, find algorithms and
657:{\displaystyle d/(2{\sqrt {k}})}
458:Instead, a different algorithm
175:{\displaystyle O(n\log \log n)}
1160:Information Processing Letters
971:
959:
893:
874:
851:
839:
816:
810:
708:, computed in the step before
651:
638:
316:-dimensional Euclidean space:
211:
196:
169:
148:
107:
94:
26:closest pair of points problem
1:
1411:Divide-and-conquer algorithms
1356:Bespamyatnikh, S. N. (1998).
899:{\displaystyle O(\log ^{2}n)}
620:be the minimum such distance.
234:divide-and-conquer algorithms
1173:10.1016/0020-0190(79)90085-1
1140:Gödel's Lost Letter and P=NP
772:Dynamic closest-pair problem
486:{\displaystyle 2{\sqrt {k}}}
1084:Information and Computation
1055:Khuller & Matias (1995)
580:to all the other points of
560:Compute the distances from
460:Khuller & Matias (1995)
1427:
1248:Introduction to Algorithms
226:element uniqueness problem
217:{\displaystyle O(n\log n)}
1327:10.1137/S0097539794277718
1314:SIAM Journal on Computing
977:{\displaystyle O(\log n)}
857:{\displaystyle O(\log n)}
537:uniformly at random from
64:of geometric algorithms.
427:surrounding grid points.
248:randomized algorithm of
120:time (expressed here in
113:{\displaystyle O(n^{2})}
62:computational complexity
999:Nearest neighbor search
420:{\displaystyle 3^{k}-1}
252:, modified slightly by
184:algebraic decision tree
1098:10.1006/inco.1995.1049
978:
943:
920:
900:
858:
823:
762:
742:
722:
702:
678:
658:
614:
594:
574:
551:
531:
507:
487:
448:
421:
377:
354:
334:
310:
290:
270:
218:
176:
114:
50:
34:computational geometry
21:
1235:Leiserson, Charles E.
1134:(24 September 2011).
979:
944:
921:
901:
859:
824:
763:
743:
723:
703:
679:
659:
615:
595:
575:
552:
532:
508:
488:
449:
422:
378:
355:
335:
311:
291:
271:
230:sweep line algorithms
219:
177:
132:models of computation
129:random-access machine
115:
51:
19:
1406:Geometric algorithms
1217:10.1109/SFCS.1983.16
1205:Clarkson, Kenneth L.
1136:"Rabin Flips a Coin"
953:
933:
910:
868:
833:
822:{\displaystyle O(n)}
804:
752:
732:
712:
692:
668:
627:
604:
584:
564:
541:
521:
497:
470:
438:
398:
367:
344:
324:
300:
280:
260:
190:
142:
88:
40:
30:closest pair problem
1031:10.1109/SFCS.1975.8
1019:Shamos, Michael Ian
464:approximation ratio
82:asymptotic analysis
1377:10.1007/PL00009340
974:
939:
916:
896:
854:
819:
758:
738:
718:
698:
674:
664:, and delete from
654:
610:
590:
570:
547:
527:
503:
483:
444:
417:
392:Moore neighborhood
373:
350:
330:
306:
286:
266:
214:
172:
110:
46:
22:
1290:978-0-321-37291-8
1273:Kleinberg, Jon M.
1239:Rivest, Ronald L.
1231:Cormen, Thomas H.
942:{\displaystyle d}
919:{\displaystyle d}
761:{\displaystyle d}
741:{\displaystyle d}
721:{\displaystyle S}
701:{\displaystyle d}
677:{\displaystyle S}
649:
613:{\displaystyle d}
593:{\displaystyle S}
573:{\displaystyle p}
550:{\displaystyle S}
530:{\displaystyle p}
506:{\displaystyle S}
481:
447:{\displaystyle d}
376:{\displaystyle d}
353:{\displaystyle d}
333:{\displaystyle n}
309:{\displaystyle k}
289:{\displaystyle n}
269:{\displaystyle S}
138:, in near-linear
49:{\displaystyle n}
1418:
1390:
1389:
1379:
1353:
1347:
1346:
1321:(4): 1036–1072.
1310:
1301:
1295:
1294:
1281:Algorithm Design
1269:
1263:
1262:
1227:
1221:
1220:
1201:
1195:
1194:
1184:
1153:Fortune, Steve;
1150:
1144:
1143:
1128:
1119:
1118:
1100:
1067:
1058:
1052:
1041:
1035:
1034:
1015:
983:
981:
980:
975:
948:
946:
945:
940:
925:
923:
922:
917:
905:
903:
902:
897:
886:
885:
863:
861:
860:
855:
828:
826:
825:
820:
767:
765:
764:
759:
747:
745:
744:
739:
727:
725:
724:
719:
707:
705:
704:
699:
683:
681:
680:
675:
663:
661:
660:
655:
650:
645:
637:
619:
617:
616:
611:
599:
597:
596:
591:
579:
577:
576:
571:
556:
554:
553:
548:
536:
534:
533:
528:
512:
510:
509:
504:
492:
490:
489:
484:
482:
477:
453:
451:
450:
445:
426:
424:
423:
418:
410:
409:
382:
380:
379:
374:
359:
357:
356:
351:
339:
337:
336:
331:
315:
313:
312:
307:
295:
293:
292:
287:
275:
273:
272:
267:
223:
221:
220:
215:
181:
179:
178:
173:
119:
117:
116:
111:
106:
105:
78:Euclidean spaces
55:
53:
52:
47:
32:is a problem of
1426:
1425:
1421:
1420:
1419:
1417:
1416:
1415:
1396:
1395:
1394:
1393:
1355:
1354:
1350:
1308:
1303:
1302:
1298:
1291:
1271:
1270:
1266:
1259:
1243:Stein, Clifford
1229:
1228:
1224:
1203:
1202:
1198:
1152:
1151:
1147:
1132:Lipton, Richard
1130:
1129:
1122:
1069:
1068:
1061:
1043:
1042:
1038:
1017:
1016:
1012:
1007:
990:
951:
950:
931:
930:
908:
907:
877:
866:
865:
831:
830:
802:
801:
790:data structures
778:dynamic version
774:
750:
749:
730:
729:
710:
709:
690:
689:
666:
665:
625:
624:
602:
601:
582:
581:
562:
561:
539:
538:
519:
518:
517:Choose a point
513:becomes empty:
495:
494:
468:
467:
436:
435:
401:
396:
395:
365:
364:
342:
341:
322:
321:
298:
297:
278:
277:
258:
257:
242:
188:
187:
140:
139:
97:
86:
85:
70:
38:
37:
12:
11:
5:
1424:
1422:
1414:
1413:
1408:
1398:
1397:
1392:
1391:
1370:(2): 175–195.
1348:
1296:
1289:
1264:
1257:
1222:
1196:
1155:Hopcroft, John
1145:
1120:
1071:Khuller, Samir
1059:
1036:
1009:
1008:
1006:
1003:
1002:
1001:
996:
989:
986:
973:
970:
967:
964:
961:
958:
938:
915:
895:
892:
889:
884:
880:
876:
873:
853:
850:
847:
844:
841:
838:
818:
815:
812:
809:
794:
793:
773:
770:
757:
737:
717:
697:
686:
685:
673:
653:
648:
643:
640:
636:
632:
621:
609:
589:
569:
558:
546:
526:
502:
480:
475:
443:
432:
431:
428:
416:
413:
408:
404:
388:
372:
361:
349:
329:
305:
285:
276:consisting of
265:
254:Richard Lipton
241:
238:
213:
210:
207:
204:
201:
198:
195:
171:
168:
165:
162:
159:
156:
153:
150:
147:
136:floor function
122:big O notation
109:
104:
100:
96:
93:
76:are known, in
69:
66:
45:
13:
10:
9:
6:
4:
3:
2:
1423:
1412:
1409:
1407:
1404:
1403:
1401:
1387:
1383:
1378:
1373:
1369:
1365:
1364:
1359:
1352:
1349:
1344:
1340:
1336:
1332:
1328:
1324:
1320:
1316:
1315:
1307:
1300:
1297:
1292:
1286:
1282:
1278:
1274:
1268:
1265:
1260:
1258:0-262-03293-7
1254:
1250:
1249:
1244:
1240:
1236:
1232:
1226:
1223:
1218:
1214:
1210:
1206:
1200:
1197:
1192:
1188:
1183:
1178:
1174:
1170:
1166:
1162:
1161:
1156:
1149:
1146:
1141:
1137:
1133:
1127:
1125:
1121:
1116:
1112:
1108:
1104:
1099:
1094:
1090:
1086:
1085:
1080:
1076:
1075:Matias, Yossi
1072:
1066:
1064:
1060:
1056:
1050:
1046:
1040:
1037:
1032:
1028:
1024:
1020:
1014:
1011:
1004:
1000:
997:
995:
992:
991:
987:
985:
968:
965:
962:
956:
936:
927:
913:
890:
887:
882:
878:
871:
848:
845:
842:
836:
813:
807:
799:
791:
787:
783:
782:
781:
779:
771:
769:
755:
735:
715:
695:
671:
646:
641:
634:
630:
622:
607:
587:
567:
559:
544:
524:
516:
515:
514:
500:
478:
473:
465:
461:
456:
441:
429:
414:
411:
406:
402:
393:
389:
386:
370:
362:
347:
327:
319:
318:
317:
303:
283:
263:
255:
251:
247:
246:expected time
239:
237:
235:
231:
227:
208:
205:
202:
199:
193:
185:
166:
163:
160:
157:
154:
151:
145:
137:
133:
130:
125:
123:
102:
98:
91:
83:
79:
75:
67:
65:
63:
59:
43:
35:
31:
27:
18:
1367:
1361:
1351:
1318:
1312:
1299:
1280:
1267:
1247:
1225:
1208:
1199:
1167:(1): 20–23.
1164:
1158:
1148:
1139:
1091:(1): 34–37.
1088:
1082:
1053:As cited by
1048:
1039:
1022:
1013:
928:
798:bounding box
795:
775:
687:
457:
433:
383:, and use a
296:points in a
250:Rabin (1976)
243:
126:
71:
58:metric space
29:
25:
23:
1277:Tardos, Éva
786:dynamic set
74:linear time
68:Time bounds
1400:Categories
385:hash table
56:points in
1182:1813/7460
1115:206566076
1045:Rabin, M.
966:
888:
846:
412:−
244:A linear
206:
164:
158:
1077:(1995).
988:See also
784:Given a
600:and let
36:: given
1386:1600047
1343:1242364
1335:1622005
1191:0515507
1107:1329236
796:If the
320:Select
228:. Both
1384:
1341:
1333:
1287:
1255:
1189:
1113:
1105:
1339:S2CID
1309:(PDF)
1111:S2CID
1005:Notes
1285:ISBN
1253:ISBN
776:The
232:and
24:The
1372:doi
1323:doi
1213:doi
1177:hdl
1169:doi
1093:doi
1089:118
1027:doi
994:GIS
963:log
879:log
843:log
466:of
394:of
203:log
161:log
155:log
28:or
1402::
1382:MR
1380:.
1368:19
1366:.
1360:.
1337:.
1331:MR
1329:.
1319:27
1317:.
1311:.
1275:;
1241:;
1237:;
1233:;
1187:MR
1185:.
1175:.
1163:.
1138:.
1123:^
1109:.
1103:MR
1101:.
1087:.
1081:.
1073:;
1062:^
1388:.
1374::
1345:.
1325::
1293:.
1261:.
1219:.
1215::
1193:.
1179::
1171::
1165:8
1142:.
1117:.
1095::
1057:.
1033:.
1029::
972:)
969:n
960:(
957:O
937:d
914:d
894:)
891:n
883:2
875:(
872:O
852:)
849:n
840:(
837:O
817:)
814:n
811:(
808:O
756:d
736:d
716:S
696:d
672:S
652:)
647:k
642:2
639:(
635:/
631:d
608:d
588:S
568:p
557:.
545:S
525:p
501:S
479:k
474:2
442:d
415:1
407:k
403:3
371:d
348:d
328:n
304:k
284:n
264:S
212:)
209:n
200:n
197:(
194:O
170:)
167:n
152:n
149:(
146:O
108:)
103:2
99:n
95:(
92:O
44:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
