Gráfico de vecino más cercano
El gráfico del vecino más próximo ( NGN ) es un gráfico dirigido definido por 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 de p a q siempre que q sea el vecino más cercano de p , un punto cuya distancia desde p es mínima entre todos los puntos dados que no sean p mismo. [1]
En muchos usos de estos gráficos, las direcciones de los bordes se ignoran y, en cambio, 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 de la definición no es necesariamente un vecino más cercano para q . En las discusiones teóricas de los algoritmos, a menudo se asume una especie 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 hay que tener en cuenta que 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 Ppuede 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 k -gráfico vecino más cercano ( k -NNG ) es un gráfico 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 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/ re norte 1 − 1/ re ) puntos. [3]
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.
Las NNG para puntos en el plano, así como en espacios multidimensionales, encuentran aplicaciones, por ejemplo, en compresión de datos , planificación de movimiento y ubicación de instalaciones . En el análisis estadístico , el algoritmo de la cadena del vecino más cercano basado en las siguientes rutas en este gráfico se puede usar para encontrar agrupaciones jerárquicas rápidamente. Los gráficos de vecinos más cercanos también son un tema de geometría computacional .
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, la NNG es un camino o un bosque de varios caminos y puede construirse en tiempo O ( n log n ) ordenando . 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 : es suficiente para verificar si el NNG tiene un borde de longitud cero. [4]
