Metraipolis › archive › dc_caf00a5be9a6

Grafo del vicino più prossimo — Wikipedia

Source

Wikipedia (it)

Original

https://it.wikipedia.org/wiki/Grafo_del_vicino_pi%C3%B9_prossimo

License (as archived)

CC-BY-SA-4.0

Archived

2026-10-07T12:05:29.046Z

SHA-256 of the archived text

1780fa83b4f485768625641a7470d91a82864b623821c9258fb2136986d276c7

Stable URL of this page

https://metraipolis.com/documento/dc_caf00a5be9a6

How to cite

Grafo del vicino più prossimo — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_del_vicino_pi%C3%B9_prossimo (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_caf00a5be9a6 (Metraipolis archive dc_caf00a5be9a6, sha256 1780fa83b4f485768625641a7470d91a82864b623821c9258fb2136986d276c7)

@misc{dccaf00a5be9a6,
  title = {Grafo del vicino più prossimo — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Grafo_del_vicino_pi%C3%B9_prossimo},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_caf00a5be9a6; sha256 1780fa83b4f485768625641a7470d91a82864b623821c9258fb2136986d276c7},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_del_vicino_pi%C3%B9_prossimo. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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ù n(d + 1)/(d + 2) 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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Grafo del vicino più prossimo» — https://it.wikipedia.org/wiki/Grafo_del_vicino_pi%C3%B9_prossimo
Wikidata Q2855103 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2855103
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Grafo_del_vicino_pi%C3%B9_prossimo?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 152355295, consultata il 2026-10-07T11:36:00.627Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: eb287d9ee07f64891b68ceed2fc61c04c869e15be1f589b76b5f8180e1cb5acf