El gráfico vecino más cercano ( NNG ) es un gráfico 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 un borde dirigido de p a q siempre que q sea el vecino más cercano de p , un punto cuya distancia de p es mínima entre todos los puntos dados distintos del propio p . [1]
En muchos usos de estos gráficos, las direcciones de los bordes se ignoran y el NNG se define como un gráfico no dirigido . Sin embargo, la relación de vecino más cercano no es simétrica , es decir, p según la definición no es necesariamente un vecino más cercano para q . En las discusiones teóricas sobre algoritmos a menudo se asume una especie de posición general , es decir, 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 esto no siempre es así. 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 caso de empate, el objeto con, por ejemplo, el índice más grande puede tomarse como el vecino más cercano. [2]
El gráfico de k vecinos más cercanos ( k -NNG ) es un gráfico en el que dos vértices p y q están conectados por un borde, si la distancia entre p y q está entre las k -ésimas distancias más pequeñas de p a otros objetos de P. El NNG es un caso especial del k -NNG, es decir, es el 1-NNG. Los k -NNG obedecen a un teorema del separador : se pueden dividir 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 se puede aproximar utilizando un algoritmo eficiente con un 90% de recuperación que es más rápido que una búsqueda de fuerza bruta en 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 alejado de él, en lugar del punto más cercano.
Los NNG para puntos en el plano y en espacios multidimensionales encuentran aplicaciones, por ejemplo, en compresión de datos , planificación de movimientos y ubicación de instalaciones . En el análisis estadístico , el algoritmo de cadena de vecinos más cercanos basado en las siguientes rutas en este gráfico se puede utilizar para encontrar agrupaciones jerárquicas rápidamente. Los gráficos del vecino más cercano 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 clasificación . Esta estimación es asintóticamente óptima para ciertos modelos de computación , porque el NNG construido da la respuesta al problema de unicidad del elemento : basta con 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.