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).^[1]

Referências

1. Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. [S.l.]: Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6