El problema de un par de puntos más cercanos

El problema del par más cercano es un  problema de geometría computacional . Dados n puntos en un espacio métrico , necesitas encontrar un par de puntos con la menor distancia entre ellos.

El problema del punto más cercano en el plano euclidiano [1] fue uno de los primeros problemas geométricos que se estudió sistemáticamente en términos de la complejidad computacional de los algoritmos geométricos .

Un algoritmo ingenuo para encontrar las distancias entre todos los pares en un espacio de dimensión d y elegir el más pequeño entre ellos toma un tiempo O ( n 2 ) . Resulta que el problema se puede resolver en el tiempo en el espacio euclidiano o en el espacio L p de dimensión fija d [2] . En el modelo de cálculo del árbol de decisión algebraico , el algoritmo con tiempo O( n log n ) es óptimo cuando se reduce del problema de unicidad de elementos . En un modelo computacional que asume que la función piso se calcula en tiempo constante, el problema puede resolverse en tiempo [3] . Si permitimos que se aplique la aleatorización junto con la función de suelo , el problema se puede resolver en O( n ) [4] [5] tiempo .

Algoritmo de fuerza bruta

El par de puntos más cercanos se puede calcular en tiempo O ( n2 ) realizando una enumeración completa . Para hacer esto, puede calcular la distancia entre todos los n ( n − 1) / 2 pares de puntos, luego elija el par con la distancia más pequeña, como se muestra a continuación.

minDist = infinito for i = 1 to length( P ) - 1 for j = i + 1 to length( P ) sea p = P [ i ], q = P [ j ] if dist ( p , q ) < minDist : minDist = dist ( p , q ) Par más cercano = ( p , q ) return Par más cercano

Caso planar

El problema se puede resolver a tiempo usando un enfoque recursivo de divide y vencerás , como este [1] :

  1. Ordena los puntos según sus coordenadas x;
  2. Dividimos el conjunto de puntos en dos subconjuntos de igual tamaño de la recta vertical ;
  3. Resolvemos el problema recursivamente en los lados izquierdo y derecho. Esto da como resultado una distancia mínima izquierda y una distancia mínima derecha , respectivamente;
  4. Encontramos la distancia mínima entre pares de puntos, de los cuales un punto está a la izquierda de la línea vertical y el otro punto está a la derecha de la línea recta;
  5. La respuesta final será el valor mínimo entre , y .

Resulta que el paso 4 se puede completar en tiempo lineal. Nuevamente, el enfoque ingenuo requeriría calcular distancias para todos los pares izquierdo/derecho, es decir, tiempo cuadrático. La observación clave se basa en la siguiente propiedad de dispersión del conjunto de puntos. Ya sabemos que el par de puntos más cercanos no están más separados que . Por lo tanto, para cada punto p a la izquierda de la línea divisoria, debemos comparar las distancias con los puntos que se encuentran en un rectángulo con dimensiones (dist, 2 ⋅ dist) como se muestra en la figura. Y este rectángulo no puede contener más de seis puntos, cuya distancia por pares no es menor que . Por lo tanto, es suficiente calcular 6 n distancias en el 4° paso [6] . La relación de recurrencia para el número de pasos se puede escribir como , que se puede resolver usando el teorema fundamental para la recurrencia divide y vencerás , que da .

Dado que un par de puntos más cercanos definen un borde en una triangulación de Delaunay y corresponden a dos celdas adyacentes en un diagrama de Voronoi , se puede determinar un par de puntos más cercanos en tiempo lineal si se da una de las dos estructuras. Calcular una triangulación de Delaunay o un diagrama de Voronoi lleva tiempo . Estos enfoques no son eficientes para dimensiones d > 2 , mientras que el algoritmo divide y vencerás se puede generalizar al tiempo de ejecución para cualquier valor constante de la dimensión d .

Problema dinámico del par más cercano

La versión dinámica para el problema de un par de puntos más cercanos se establece de la siguiente manera:

Si se conoce de antemano el cuadro delimitador de todos los puntos y se dispone de una función de suelo con tiempo de ejecución constante, se propuso una estructura de datos con una memoria esperada de O( n ) que admita un tiempo esperado (tiempo promedio) de inserción y eliminación de O(log n ) y un tiempo de consulta constante. Si el problema se modifica para un modelo de árbol de decisión algebraico, las inserciones y eliminaciones requerirán un tiempo promedio [7] . Cabe señalar que la complejidad del problema dinámico anterior de un par de puntos más cercanos depende exponencialmente de la dimensión d , por lo que el algoritmo se vuelve menos adecuado para problemas de alta dimensión.

Un algoritmo para el problema dinámico de un par de puntos más cercanos en un espacio de dimensión d fue desarrollado por Sergey Bespamyatnykh en 1998 [8] . Los puntos se pueden insertar y eliminar en O (log n ) tiempo por punto (peor caso).

Véase también

Notas

  1. ↑ 12 Shamos , Hoey, 1975 , pág. 151-162.
  2. ↑ Clarkson, 1983 .
  3. ↑ Fortune, Hopcroft, 1979 , pág. 20-23.
  4. ↑ Khuller y Matías 1995 , p. 34-37.
  5. ↑ Ricardo Lipton. Rabin lanza una moneda (24 de septiembre de 2011). Consultado el 19 de febrero de 2019. Archivado desde el original el 16 de febrero de 2019.
  6. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 957-961 33.4: Encontrar el par de puntos más cercano.
  7. ↑ Golin, Raman, Schwarz, Smid, 1998 .
  8. ↑ Bespamyatnikh, 1998 , pág. 175-195.

Literatura