20:
110:
is often assumed, namely, the nearest (k-nearest) neighbor is unique for each object. In implementations of the algorithms it is necessary to bear in mind that this is not always the case. For situations in which it is necessary to make the nearest neighbor for each object unique, the set
313:
261:
For a set of points on a line, the nearest neighbor of a point is its left or right (or both) neighbor, if they are sorted along the line. Therefore, the NNG is a
334:
The NNG (treated as an undirected graph with multiple nearest neighbors allowed) of a set of points in the plane or any higher dimension is a subgraph of the
305:
Unless stated otherwise, it is assumed that the NNGs are digraphs with uniquely defined nearest neighbors as described in the introduction.
550:
Aggarwal, Alok; Kipnis, Shlomo (August 1988). "Lecture #10, March 10, 1988: Closest pair". In
Aggarwal, Alok; Wein, Joel (eds.).
578:
432:
115:
may be indexed and in the case of a tie the object with, e.g., the largest index may be taken as the nearest neighbor.
526:
392:
230:
351:
210:(FNG), in which each point is connected by an edge to the farthest point from it, instead of the nearest point.
346:. If the points are in general position or if the single nearest neighbor condition is imposed, the NNG is a
90:
In many uses of these graphs, the directions of the edges are ignored and the NNG is defined instead as an
294:
606:
222:
169:
461:
238:
335:
286:
242:
213:
NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in
554:. Massachusetts Institute of Technology Laboratory for Computer Science. Observation 1, p. 2.
290:
266:
56:
198:-NNG can be approximated using an efficient algorithm with 90% recall that is faster than a
226:
8:
372:
347:
262:
234:
532:
376:
199:
95:
48:
536:
522:
506:
397:. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989.
388:
582:
514:
485:
469:
441:
328:
214:
107:
91:
52:
507:"Efficient k-nearest neighbor graph construction for generic similarity measures"
384:
218:
24:
575:
Kinetic data structures for all nearest neighbors and closest pair in the plane
570:
465:
415:
343:
270:
40:
600:
419:
339:
324:
248:
The method can be used to induce a graph on nodes with unknown connectivity.
60:
586:
518:
566:
320:
44:
490:
473:
371:
423:
19:
446:
427:
309:
Along any directed path in an NNG the edge lengths are non-increasing.
297:: it is sufficient to check whether the NNG has a zero-length edge.
511:
Proceedings of the 20th international conference on World wide web
282:
579:
102:
from the definition is not necessarily a nearest neighbor for
552:
Computational
Geometry: Lecture Notes for 18.409, Spring 1988
474:"Separators for sphere-packings and nearest neighbor graphs"
316:
of an NNG with at least 2 vertices has exactly one 2-cycle.
513:. Association for Computing Machinery. pp. 577–586.
460:
312:
Only cycles of length 2 are possible in an NNG and each
172:: they can be partitioned into two subgraphs of at most
241:
quickly. Nearest neighbor graphs are also a subject of
293:, because the constructed NNG gives the answer to the
564:
505:
Dong, Wei; Moses, Charikar; Li, Kai (28 March 2011).
106:. In theoretical discussions of algorithms a kind of
414:
478:Journal of the Association for Computing Machinery
140:are connected by an edge, if the distance between
94:. However, the nearest neighbor relation is not a
83:is minimum among all the given points other than
598:
549:
23:A nearest neighbor graph of 100 points in the
504:
269:of several paths and may be constructed in
251:
489:
445:
319:For the points in the plane the NNG is a
381:Computational Geometry - An Introduction
18:
256:
599:
558:
410:
408:
406:
404:
300:
433:Discrete and Computational Geometry
160:. The NNG is a special case of the
132:) is a graph in which two vertices
13:
401:
237:in this graph can be used to find
187:vertices each by the removal of O(
14:
618:
43:defined for a set of points in a
231:nearest-neighbor chain algorithm
352:Euclidean minimum spanning tree
543:
498:
472:; Vavasis, Stephen A. (1997).
454:
365:
164:-NNG, namely it is the 1-NNG.
79:, a point whose distance from
1:
358:
202:by an order of magnitude.
428:"On nearest-neighbor graphs"
327:at most 6. If points are in
152:-th smallest distances from
7:
10:
623:
331:, the degree is at most 5.
314:weakly connected component
295:element uniqueness problem
206:Another variation is the
75:is a nearest neighbor of
239:hierarchical clusterings
123:-nearest neighbors graph
587:10.1145/2462356.2462378
519:10.1145/1963405.1963487
252:NNGs for sets of points
208:farthest neighbor graph
336:Delaunay triangulation
287:asymptotically optimal
243:computational geometry
156:to other objects from
59:for each point, and a
33:nearest neighbor graph
28:
16:Type of directed graph
491:10.1145/256292.256294
291:models of computation
22:
581:. pp. 137–144.
350:, a subgraph of the
257:One-dimensional case
227:statistical analysis
373:Franco P. Preparata
285:. This estimate is
233:based on following
223:facilities location
447:10.1007/PL00009293
377:Michael Ian Shamos
200:brute-force search
49:Euclidean distance
29:
470:Thurston, William
301:Higher dimensions
170:separator theorem
614:
607:Geometric graphs
591:
590:
562:
556:
555:
547:
541:
540:
502:
496:
495:
493:
458:
452:
451:
449:
412:
399:
398:
369:
329:general position
215:data compression
186:
108:general position
92:undirected graph
55:. The NNG has a
622:
621:
617:
616:
615:
613:
612:
611:
597:
596:
595:
594:
563:
559:
548:
544:
529:
503:
499:
466:Teng, Shang-Hua
462:Miller, Gary L.
459:
455:
420:Paterson, M. S.
413:
402:
395:
385:Springer-Verlag
370:
366:
361:
303:
259:
254:
219:motion planning
205:
173:
25:Euclidean plane
17:
12:
11:
5:
620:
610:
609:
593:
592:
571:Whitesides, S.
557:
542:
527:
497:
453:
440:(3): 263–282.
400:
393:
363:
362:
360:
357:
356:
355:
344:Semi-Yao graph
332:
325:vertex degrees
317:
310:
302:
299:
258:
255:
253:
250:
47:, such as the
41:directed graph
15:
9:
6:
4:
3:
2:
619:
608:
605:
604:
602:
588:
584:
580:
576:
572:
568:
565:Rahmati, Z.;
561:
553:
546:
538:
534:
530:
528:9781450306324
524:
520:
516:
512:
508:
501:
492:
487:
483:
479:
475:
471:
467:
463:
457:
448:
443:
439:
435:
434:
429:
425:
421:
417:
411:
409:
407:
405:
396:
394:0-387-96131-3
390:
386:
382:
378:
374:
368:
364:
353:
349:
345:
341:
340:Gabriel graph
337:
333:
330:
326:
322:
318:
315:
311:
308:
307:
306:
298:
296:
292:
288:
284:
280:
276:
272:
268:
264:
249:
246:
244:
240:
236:
232:
228:
224:
220:
216:
211:
209:
203:
201:
197:
193:
190:
184:
180:
176:
171:
168:-NNGs obey a
167:
163:
159:
155:
151:
148:is among the
147:
143:
139:
135:
131:
129:
124:
122:
116:
114:
109:
105:
101:
97:
96:symmetric one
93:
88:
86:
82:
78:
74:
70:
66:
62:
61:directed edge
58:
54:
50:
46:
42:
38:
34:
26:
21:
574:
560:
551:
545:
510:
500:
481:
477:
456:
437:
431:
424:Yao, Frances
416:Eppstein, D.
380:
367:
321:planar graph
304:
289:for certain
278:
274:
260:
247:
212:
207:
204:
195:
194:) points. A
191:
188:
182:
178:
174:
165:
161:
157:
153:
149:
145:
141:
137:
133:
127:
126:
120:
119:
117:
112:
103:
99:
89:
84:
80:
76:
72:
68:
64:
45:metric space
36:
32:
30:
484:(1): 1–29.
359:References
342:, and the
281:) time by
537:207186093
71:whenever
53:the plane
601:Category
573:(2013).
567:King, V.
426:(1997).
379:(1985).
98:, i.e.,
87:itself.
283:sorting
39:) is a
535:
525:
391:
348:forest
338:, the
267:forest
229:, the
221:, and
181:+ 1)/(
57:vertex
533:S2CID
323:with
265:or a
235:paths
225:. In
144:and
63:from
523:ISBN
389:ISBN
375:and
277:log
263:path
185:+ 2)
136:and
130:-NNG
118:The
31:The
583:doi
515:doi
486:doi
442:doi
67:to
51:in
37:NNG
603::
577:.
569:;
531:.
521:.
509:.
482:44
480:.
476:.
468:;
464:;
438:17
436:.
430:.
422:;
418:;
403:^
387:.
383:.
245:.
217:,
589:.
585::
539:.
517::
494:.
488::
450:.
444::
354:.
279:n
275:n
273:(
271:O
196:k
192:n
189:k
183:d
179:d
177:(
175:n
166:k
162:k
158:P
154:p
150:k
146:q
142:p
138:q
134:p
128:k
125:(
121:k
113:P
104:q
100:p
85:p
81:p
77:p
73:q
69:q
65:p
35:(
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
