Grafo do vizinho mais próximo

Um grafo do vizinho mais próximo de 100 pontos no plano euclideano.

O grafo do vizinho mais próximo (citado e abreviado na literatura em inglês como NNG, de nearest neighbor graph) para um conjunto de n objetos P num espaço métrico (e.g., para um conjunto de pontos no plano com distâncias euclidianas) é um grafo direto com P sendo seu conjunto de vértices definido e com uma aresta direcionada de p a q sempre que q é um vizinho mais próximo de p (i.e., a distância de p a q não é maior que de p a qualquer outro objeto de P).