Gráfica de vecinos más cercanos

Un grafo de vecino más próximo ( GBC ) para un conjunto P que consta de n objetos en un espacio métrico (por ejemplo, para un conjunto de puntos en un plano con una métrica euclidiana ) es un grafo dirigido cuyos vértices son elementos del conjunto P , en que hay un borde dirigido de p a q , si q es el vecino más cercano de p (es decir, la distancia de p a q no es mayor que la de p a cualquier otro objeto en P )[1] .

En muchas discusiones, la dirección de los bordes se ignora y el GBS 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, si q es el vecino más cercano de p , entonces p no es necesariamente el vecino más cercano de q .

En algunas discusiones, para hacer que la elección del vecino más cercano sea única, el conjunto P se indexa y cuando se elige el objeto más cercano, se elige el objeto con el índice más alto [2] .

Un gráfico de vecino más cercano k ( k -GBN ) 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 distancias más pequeñas de p a otros objetos en P. GBS es un caso especial de k -GBS, es decir, es 1-GBS. k -GBS satisfacen las condiciones del teorema de partición plana - se pueden dividir en dos subgrafos con un máximo de vértices eliminando ) puntos [3] .

Otro caso especial es el ( n  − 1)-GBS. Este gráfico se denomina gráfico de vecino lejano (FDN).

En las discusiones teóricas de los algoritmos, a menudo se asume algún tipo de posición general , a saber, que para cada objeto, el vecino más cercano (k-más cercano) es único. Al implementar algoritmos, se debe tener en cuenta que esta condición no siempre se cumple.

GDS, tanto para puntos en el plano como para puntos en espacios multidimensionales, encuentran aplicaciones, por ejemplo, en compresión de datos , para planificación de movimiento y colocación de objetos . En el análisis estadístico , el algoritmo de la cadena del vecino más cercano basado en las rutas de este gráfico se puede usar para encontrar rápidamente agrupaciones jerárquicas . Los gráficos de vecinos más cercanos también son un tema de geometría computacional .

Gráficos de vecinos más cercanos para conjuntos de puntos

Caso unidimensional

Para un conjunto de puntos en un plano, el vecino más cercano de un punto es el vecino izquierdo o derecho (o ambos) si están ordenados a lo largo de una línea recta. Por lo tanto, un GBS es un camino o un bosque de varios caminos y se puede construir en tiempo O ( n log n ) ordenando . Esta estimación es asintóticamente óptima para algunos modelos computacionales , ya que el GBS construido da la respuesta al problema de la unicidad del elemento : es suficiente para verificar si el GBS resultante contiene un borde de longitud cero.

Dimensiones superiores

A menos que se indique explícitamente, se supone que los gráficos de vecinos más cercanos son gráficos dirigidos con vecinos definidos de forma única, como se describe en la introducción.

  1. A lo largo de cualquier camino orientado en GBS, las longitudes de los bordes no aumentan [2] .
  2. Solo son posibles ciclos de longitud 2 en GBS, y cada componente GDS débilmente conectado con 2 o más vértices tiene exactamente un ciclo 2 [2] .
  3. Para puntos planos, GBS es un gráfico plano con grados de vértice que no exceden 6. Si los puntos están en posición general , el grado de vértice no excede 5 [2] .
  4. El GBS (considerado como un grafo no dirigido con resolución de múltiples vecinos más cercanos) de un conjunto de puntos en un plano o cualquier espacio de mayor dimensión es un subgrafo de una triangulación de Delaunay , un grafo de Gabriel y un grafo semi-Y [ 4] . Si los puntos están en una posición común, o si se impone la condición única de vecino más cercano, el GBS es un bosque , un subgrafo del árbol de expansión mínimo euclidiano .

Notas

  1. ↑ Preparata, Sheimos, 1989 .
  2. ↑ 1 2 3 4 Eppstein, Paterson, Yao, 1997 , pág. 263–282.
  3. ↑ Miller, Teng, Thurston, Vavasis, 1997 .
  4. ↑ Rahmati, King, Whitesides, 2013 , pág. 137–144.

Literatura

Enlaces