El gráfico vecino más cercano ( NNG ) para un conjunto de n objetos P en un espacio métrico (por ejemplo, para un conjunto de puntos en el plano con distancia euclidiana ) es un gráfico dirigido con P como conjunto de vértices y con una arista dirigida desde p a q siempre que q sea un vecino más cercano de p (es decir, la distancia de p a q no es mayor que de p a cualquier otro objeto de P ). [1]
En muchas discusiones se ignoran las direcciones de los bordes y el NNG se define como un gráfico ordinario (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 algunas discusiones, para que el vecino más cercano para cada objeto sea único, el conjunto P se indexa y, en el caso de un vínculo, el objeto con, por ejemplo, el índice más grande se toma para el vecino más cercano. [2]
El k -nearest gráfico vecino ( k -NNG ) es un gráfico en el que dos vértices p y q están conectadas por un borde, si la distancia entre p y q es uno de los k -ésimos 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]
Otro caso especial es el ( n - 1) -NNG. Este gráfico se denomina gráfico de vecino más lejano (FNG).
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 no siempre es así.
Los 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 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 .
NNG para conjuntos de puntos
Caso unidimensional
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 se puede construir en tiempo O ( n log n ) clasificando . Esta estimación es asintóticamente óptima para ciertos modelos de cálculo , porque el NNG construido da la respuesta al problema de la unicidad del elemento : es suficiente comprobar si el NNG tiene un borde de longitud cero. [4]
Mayores dimensiones
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.
- A lo largo de cualquier trayectoria dirigida en un NNG, las longitudes de los bordes no aumentan. [2]
- Solo los ciclos de longitud 2 son posibles en un NNG y cada componente débilmente conectado de un NNG con al menos 2 vértices tiene exactamente un ciclo de 2. [2]
- Para los puntos en el plano, el NNG es un gráfico plano con grados de vértice como máximo 6. Si los puntos están en posición general , el grado es como máximo 5. [2]
- El NNG (tratado como un gráfico no dirigido con múltiples vecinos más cercanos permitidos) de un conjunto de puntos en el plano o cualquier dimensión superior es un subgráfico de la triangulación de Delaunay , el gráfico de Gabriel y el gráfico Semi-Yao . [5] Si los puntos están en posición general o si se impone la condición de vecino único más cercano, el NNG es un bosque , un subgrafo del árbol de expansión mínimo euclidiano .
Referencias
- ^ Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag . ISBN 0-387-96131-3. 1ª edición:; Segunda impresión, corregida y ampliada, 1988:; Traducción rusa, 1989.
- ^ a b c d Eppstein, D .; Paterson, MS ; Yao, Frances (1997). "En gráficos de vecinos más cercanos" . Geometría discreta y computacional . 17 (3): 263-282. doi : 10.1007 / PL00009293 .
- ^ Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997). "Separadores para empaquetaduras de esferas y gráficos de vecinos más cercanos". J. ACM . 44 (1): 1–29. doi : 10.1145 / 256292.256294 .
- ^ Aggarwal, Alok; Kipnis, Shlomo (agosto de 1988). "Conferencia # 10, 10 de marzo de 1988: pareja más cercana". En Aggarwal, Alok; Wein, Joel (eds.). Geometría computacional: Notas de clase para 18.409, primavera de 1988 . Laboratorio del Instituto Tecnológico de Massachusetts para Ciencias de la Computación. Observación 1, pág. 2.
- ^ Rahmati, Z .; King, V .; Whitesides, S. (2013). Estructuras de datos cinéticas para todos los vecinos más cercanos y el par más cercano en el plano . Actas del 29º Simposio ACM sobre geometría computacional . págs. 137-144. doi : 10.1145 / 2462356.2462378 .
enlaces externos
- Biblioteca C ++ para la construcción eficiente de grafos del vecino más cercano