miniatura|240x240px|Un gràfic de veïnes més properes de 100 punts en el pla euclidià. El gràfic del veí més proper (NNG) és un gràfic dirigit definit per a un conjunt de punts en un espai mètric, com ara la distància euclidiana en el pla. El NNG té un vèrtex per a cada punt, i una vora dirigida de p a q sempre que q sigui el veí més proper de p, un punt la distància del qual des de p és mínima entre tots els punts donats que no sigui p mateix.

En molts usos d'aquests gràfics, les direccions de les vores s'ignoren i el NNG es defineix com un gràfic no dirigit. Tanmateix, la relació de veí més proper no és simètrica, és a dir, p de la definició no és necessàriament un veí més proper per a q. En les discussions teòriques sobre algorismes sovint s'assumeix una mena de posició general, és a dir, el veí més proper (k-més proper) és únic per a cada objecte. En les implementacions dels algorismes cal tenir en compte que no sempre és així. Per a situacions en què cal fer únic el veí més proper per a cada objecte, es pot indexar el conjunt P i, en cas d'empat, l'objecte amb, per exemple, l'índex més gran es pot prendre com el veí més proper.

El gràfic de k -veïns més propers (k -NNG) és un gràfic en el qual dos vèrtexs p i q estan connectats per una aresta, si la distància entre p i q es troba entre les k -estimes distàncies més petites de p a altres objectes de P. El NNG és un cas especial del k -NNG, és a dir, és el 1-NNG. Els k -NNG obeeixen a un teorema de separació: es poden dividir en dos subgrafs de com a màxim vèrtexs cadascun eliminant O(k1/d n1−1/d) punts. Un k -NNG es pot aproximar mitjançant un algorisme eficient amb un 90% de record que és més ràpid que una cerca de força bruta per un ordre de magnitud.

Una altra variació és el gràfic del veí més llunyà (FNG), en què cada punt està connectat per una aresta amb el punt més allunyat d'ell, en lloc del punt més proper.

Els NNG per a punts del pla i d'espais multidimensionals troben aplicacions, per exemple, en compressió de dades, planificació del moviment i ubicació d'instal·lacions. En l'anàlisi estadística, l'algorisme de la cadena del veí més proper basat en els camins següents en aquest gràfic es pot utilitzar per trobar agrupacions jeràrquiques ràpidament. Els gràfics de veïns més propers també són un tema de geometria computacional.

El mètode es pot utilitzar per induir un gràfic en nodes amb connectivitat desconeguda.

NNG per a conjunts de punts Cas unidimensional Per a un conjunt de punts d'una línia, el veí més proper d'un punt és el seu veí esquerre o dret (o tots dos), si estan ordenats al llarg de la línia. Per tant, el NNG és un camí o un bosc de diversos camins i es pot construir en un temps O(nlogn) mitjançant l'ordenació. Aquesta estimació és asimptòticament òptima per a certs models de càlcul, perquè el NNG construït dona la resposta al problema de la unicitat de l'element: és suficient per comprovar si el NNG té una vora de longitud zero.

Dimensions superiors A menys que s'indiqui el contrari, se suposa que els NNG són dígrafs amb els veïns més propers definits de manera única, tal com es descriu a la introducció.

Al llarg de qualsevol camí dirigit en un NNG, les longituds de les vores no augmenten. Només els cicles de longitud 2 són possibles en un NNG i cada component feblement connectat d'un NNG amb almenys 2 vèrtexs té exactament un cicle de 2. Per als punts del pla, el NNG és un gràfic pla amb graus de vèrtex com a màxim 6. Si els punts estan en posició general, el grau és com a màxim 5. El NNG (tractat com un gràfic no dirigit amb múltiples veïns més propers permesos) d'un conjunt de punts del pla o de qualsevol dimensió superior és un subgraf de la triangulació de Delaunay, el gràfic de Gabriel i el gràfic Semi-Yao. Si els punts estan en posició general o si s'imposa la condició de veí més proper, el NNG és un bosc, un subgraf de l'arbre spanning mínim euclidià.

Referències

Categoria:Distància