El grafo del vecino más próximo ( NNG ) es un grafo dirigido definido para un conjunto de puntos en un espacio métrico , como la distancia euclidiana en el plano . El NNG tiene un vértice para cada punto y una arista dirigida desde p hasta q siempre que q sea un vecino más próximo de p , un punto cuya distancia desde p es mínima entre todos los puntos dados excepto p mismo. [1]
En muchos usos de estos grafos, se ignoran las direcciones de los bordes y el NNG se define en cambio como un grafo no dirigido . Sin embargo, la relación de vecino más cercano no es simétrica , es decir, p de la definición no es necesariamente un vecino más cercano para q . En las discusiones teóricas de algoritmos a menudo se asume un tipo de posición general , a saber, el vecino más cercano (k-más cercano) es único para cada objeto. En las implementaciones de los algoritmos es necesario tener en cuenta que este no siempre es el caso. Para situaciones en las que es necesario hacer que el vecino más cercano para cada objeto sea único, el conjunto P puede indexarse y en el caso de un empate el objeto con, por ejemplo, el índice más grande puede tomarse como el vecino más cercano. [2]
El grafo de vecinos k -más cercanos ( k -NNG ) es un grafo en el que dos vértices p y q están conectados por una arista, si la distancia entre p y q está entre las k -ésimas distancias más pequeñas de p a otros objetos desde P . El NNG es un caso especial del k -NNG, es decir, es el 1-NNG. Los k -NNG obedecen a un teorema separador : pueden dividirse en dos subgrafos de como máximo n ( d + 1)/( d + 2) vértices cada uno mediante la eliminación de O( k 1/ d n 1 − 1/ d ) puntos. [3] Un k -NNG puede aproximarse utilizando un algoritmo eficiente con un 90% de recuperación que es más rápido que una búsqueda de fuerza bruta por un orden de magnitud. [4]
Otra variación es el gráfico del vecino más lejano (FNG), en el que cada punto está conectado por un borde al punto más lejano, en lugar del punto más cercano.
Los NNG para puntos en el plano, así como en espacios multidimensionales, encuentran aplicaciones, por ejemplo, en la compresión de datos , la planificación de movimiento y la ubicación de instalaciones . En el análisis estadístico , el algoritmo de cadena de vecinos más cercanos basado en el seguimiento de rutas en este gráfico se puede utilizar para encontrar agrupaciones jerárquicas rápidamente. Los gráficos de vecinos más cercanos también son un tema de geometría computacional .
El método se puede utilizar para inducir un gráfico en nodos con conectividad desconocida.
Para un conjunto de puntos en una línea, el vecino más cercano de un punto es su vecino izquierdo o derecho (o ambos), si están ordenados a lo largo de la línea. Por lo tanto, el NNG es un camino o un bosque de varios caminos y puede construirse en tiempo O ( n log n ) mediante ordenamiento . Esta estimación es asintóticamente óptima para ciertos modelos de computación , porque el NNG construido da la respuesta al problema de unicidad de elementos : es suficiente verificar si el NNG tiene un borde de longitud cero. [5]
A menos que se indique lo contrario, se supone que los NNG son dígrafos con vecinos más cercanos definidos de forma única, como se describe en la introducción.