Hispanopedia Wiki
Articulo de referencia

Grafo del vecino más cercano

Un gráfico de vecinos más cercanos de 100 puntos en el plano euclidiano . El grafo de vecinos más cercanos ( NNG ) es un grafo dirigido definido para un conjunto de puntos en un...

Hispanopedia WikiContenido en espanolLectura gratuita
Un gráfico de vecinos más cercanos de 100 puntos en el plano euclidiano .

El grafo de vecinos más cercanos ( 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 de p a q siempre que q sea el vecino más cercano de p , es decir, un punto cuya distancia a p es mínima entre todos los puntos dados, excluyendo a p mismo. [ 1 ]

En muchos usos de estos grafos, se ignoran las direcciones de las aristas y el NNG se define como un grafo no dirigido . Sin embargo, la relación del vecino más cercano no es simétrica , es decir, p , según la definición, no es necesariamente el vecino más cercano de q . En las discusiones teóricas sobre algoritmos, a menudo se asume una posición general : el vecino más cercano (k-vecinos más cercanos) 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 que el vecino más cercano de 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 grafo de k vecinos 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 se encuentra entre las k distancias más pequeñas de p a otros objetos de P. El NNG es un caso especial del k -NNG, concretamente el 1-NNG. Los k -NNG obedecen un teorema de separación : pueden particionarse en dos subgrafos de como máximo n ( d +1)/( d +2) vértices cada uno mediante la eliminación de O( k1 / dn1-1 / d ) puntos. [ 3 ] Un k -NNG puede aproximarse utilizando un algoritmo eficiente con un 90% de recuperación que es un orden de magnitud más rápido que una búsqueda por fuerza bruta . [ 4 ]  

Otra variante es el grafo del vecino más lejano (FNG, por sus siglas en inglés), en el que cada punto está conectado por una arista al punto más alejado de él, en lugar de al punto más cercano.

Los grafos de vecinos más cercanos (NNG) para puntos en el plano y en espacios multidimensionales encuentran aplicaciones, por ejemplo, en la compresión de datos , la planificación de movimiento y la localizació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 grafo, puede utilizarse para encontrar agrupaciones jerárquicas rápidamente. Los grafos de vecinos más cercanos también son objeto de estudio en geometría computacional .

Este método puede utilizarse para generar un grafo a partir de nodos con conectividad desconocida.

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 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 de elementos : es suficiente comprobar si el NNG tiene una arista de longitud cero. [ 5 ]

Dimensiones superiores

Salvo que se indique lo contrario, se asume que los NNG son digrafos con vecinos más cercanos definidos de forma única, tal como se describe en la introducción.

  1. A lo largo de cualquier camino dirigido en un NNG, las longitudes de los bordes no son crecientes. [ 2 ]
  2. En un NNG solo son posibles ciclos de longitud 2, y cada componente débilmente conexa de un NNG con al menos 2 vértices tiene exactamente un ciclo de longitud 2. [ 2 ]
  3. Para los puntos en el plano, el NNG es un grafo planar 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 ]
  4. El NNG (tratado como un grafo no dirigido con múltiples vecinos más cercanos permitidos) de un conjunto de puntos en el plano o en cualquier dimensión superior es un subgrafo de la triangulación de Delaunay , el grafo de Gabriel y el grafo Semi-Yao . [ 6 ] Si los puntos están en posición general o si se impone la condición de un único vecino más cercano, el NNG es un bosque , un subgrafo del árbol de expansión mínima euclidiana .

Referencias

  1. ↑ Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag . ISBN 0-387-96131-3. 1.ª edición; 2.ª reimpresión, corregida y ampliada, 1988; traducción al ruso, 1989.
  2. 1 2 3 4 Eppstein, D. ; Paterson, MS ; Yao, Frances (1997). "Sobre grafos de vecinos más cercanos" . Geometría discreta y computacional . 17 (3): 263– 282. doi : 10.1007/PL00009293 .
  3. ↑ Miller, Gary L. ; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997). "Separadores para empaquetamientos de esferas y grafos de vecinos más cercanos" . Journal of the Association for Computing Machinery . 44 (1): 1– 29. doi : 10.1145/256292.256294 .
  4. ↑ Dong, Wei; Moses, Charikar; Li, Kai (28 de marzo de 2011). «Construcción eficiente de grafos de k vecinos más cercanos para medidas de similitud genéricas» . Actas de la 20.ª conferencia internacional sobre la World Wide Web . Association for Computing Machinery. págs. 577–586 . doi : 10.1145/1963405.1963487 . ISBN  9781450306324. S2CID 207186093 . 
  5. ↑ Aggarwal, Alok; Kipnis, Shlomo (agosto de 1988). "Clase n.° 10, 10 de marzo de 1988: Par más cercano". En Aggarwal, Alok; Wein, Joel (eds.). Geometría computacional: Apuntes de clase para 18.409, primavera de 1988. Laboratorio de Ciencias de la Computación del Instituto Tecnológico de Massachusetts. Observación 1, pág. 2.
  6. ↑ Rahmati, Z.; King, V. ; Whitesides, S. (2013). Estructuras de datos cinéticos 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 .