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