Il grafo del vicino più prossimo (in inglese nearest neighbor graph, NNG) è un grafo orientato definito per un insieme di punti in uno spazio metrico, come un piano con la distanza euclidea. Tale grafo ha un vertice per ogni punto e un arco orientato da p al vertice q se q è un vicino più prossimo di p, un punto la cui distanza da p sia minimale tra tutti i punti dati diversi da p stesso.

In molti metodi che usano questi grafi, le direzioni degli archi vengono ignorate e l'NNG viene definito invece come un grafo non orientato. Tuttavia, la relazione di vicinato più prossimo non è simmetrica, ossia il punto p dalla definizione non è necessariamente un vicino più prossimo per q. Nelle discussioni teoriche sugli algoritmi si fa spesso una sorta di assunzione generale, che vuole che il vicino più prossimo (o l'insieme dei k vicini più prossimi) sia unico per ogni oggetto. Nelle implementazioni degli algoritmi è necessario tenere presente che questo vale sempre. In situazioni nelle quali è necessario rendere unico il vicino più prossimo per ogni oggetto, si può adottare un indice e, in caso di parità, l'oggetto con, ad esempio, l'indice più grande può essere assunto come vicino più prossimo.

Il grafo dei k vicini più prossimi (k-NNG) è un grafo in cui due vertici p e q sono connessi da un arco, se la distanza tra p e q è tra le k -esime distanze più piccole da p di altri oggetti da p. Un NNG è un caso speciale del k-NNG, ovvero è l'1-NNG. I k-NNG obbediscono a un teorema di separazione: possono essere partizionati in due sottografi con al più vertici ciascuno mediante la rimozione di O(k1/ d n 1−1/ d ) punti. Un k-NNG può essere approssimato utilizzando un algoritmo efficiente con un richiamo del 90% che è di un ordine di grandezza più veloce rispetto alla ricerca a forza bruta.

Un'altra variante è il grafo del vicino più lontano (FNG), in cui ogni punto è collegato tramite un arco al punto più distante da esso, invece che a quello più vicino.

I grafi dei vicini più prossimi (NNG) per punti nel piano e in spazi multidimensionali trovano applicazioni, ad esempio, nella compressione dei dati, nella pianificazione del movimento e nell'allocazione di risorse. Nell'analisi statistica, gli algoritmi di concatenazione di archi verso vicini basato sull'individuazione di percorsi in questo tipo di grafo, può essere utilizzato per trovare rapidamente raggruppamenti gerarchici. I grafi dei vicini più prossimi sono anche oggetto di studio nella geometria computazionale.

Il metodo può essere utilizzato per indurre un grafo con nodi dalla connettività sconosciuta.

Grafi dei vicini più prossimi per insiemi di punti

Caso unidimensionale Per un insieme di punti su una retta, il vicino più prossimo di un punto è il suo vicino sinistro o destro (o entrambi), se sono ordinati lungo la retta. Pertanto, l'NNG è un percorso o una foresta di diversi percorsi e può essere costruito in tempo O(n log n) mediante ordinamento. Questa stima è asintoticamente ottimale per certi modelli di calcolo, perché l'NNG costruito fornisce la risposta al problema dell'unicità degli elementi: è sufficiente verificare se l'NNG ha un arco di lunghezza zero.

Dimensioni maggiori Salvo diversa indicazione, si assume che gli NNG siano digrafi con vicini più prossimi determinati in modo univoco, così come descritto nell'introduzione.

Lungo qualsiasi percorso orientato in un NNG le lunghezze degli spigoli non sono crescenti. In un NNG sono possibili solo cicli di lunghezza 2 e ogni componente debolmente connessa di un NNG con almeno 2 vertici ha esattamente un ciclo di lunghezza 2. Per i punti nel piano l'NNG è un grafo planare con gradi dei vertici al massimo 6. Se i punti sono in posizione generale, il grado è al massimo 5. L'NNG (trattato come un grafo non orientato con più vicini prossimi consentiti) di un insieme di punti nel piano o in qualsiasi dimensione superiore è un sottografo della triangolazione di Delaunay, del grafo di Gabriel e del grafo di Semi-Yao. Se i punti sono in posizione generale o se viene imposta la condizione del singolo vicino più prossimo, l'NNG è una foresta, un sottografo dell'albero di copertura minimo euclideo.

Note

Categoria:Teoria dei grafi