Grafo del vecino más cercano

El grafo del vecino más cercano (en inglés, nearest neighbor graph o NNG) de un conjunto de objetos en un espacio métrico (generalmente, un conjunto de puntos en el plano euclídeo) es un grafo dirigido donde cada nodo representa a uno de los objetos y donde existe una arista entre cada nodo y su nodo más cercano.^[1]​

Grafo del vecino más cercano de 100 puntos en el Plano euclídeo.

En muchas aplicaciones se suele ignorar la dirección de las aristas, convirtiendo el grafo dirigido en un grafo no dirigido. En cualquier caso, la relación de "vecino más cercano" no es una relación simétrica, es decir, que P sea el objeto más cercano a Q, no implica que Q sea el objeto más cercano a P. ^[2]​

Referencias y enlaces externos

1. Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. 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. 
2. Eppstein, D.; Paterson, M. S.; Yao, Frances (1997). «On nearest-neighbor graphs». Discrete and Computational Geometry 17 (3): 263-282. doi:10.1007/PL00009293. 

•   Datos: Q2855103