Problema del par de puntos más cercanos

El problema del par de puntos más cercanos o problema del par más cercano es un problema de geometría computacional : dado${\displaystyle n}$Puntos en el espacio métrico , encontrar un par de puntos con la menor distancia entre ellos. El problema del par más cercano para puntos en el plano euclidiano ^{[ 1 ]} fue uno de los primeros problemas geométricos que se trataron en los orígenes del estudio sistemático de la complejidad computacional de los algoritmos geométricos.

Se conocen algoritmos aleatorios que resuelven el problema en tiempo lineal , en espacios euclidianos cuya dimensión se trata como una constante para los fines del análisis asintótico . ^{[ 2 ] [ 3 ] [ 4 ]} Esto es significativamente más rápido que el${\displaystyle O(n^{2})}$tiempo (expresado aquí en notación O grande ) que se obtendría mediante un algoritmo ingenuo de encontrar distancias entre todos los pares de puntos y seleccionar la más pequeña.

También es posible resolver el problema sin aleatorización, en modelos de computación de acceso aleatorio con memoria ilimitada que permiten el uso de la función piso , en sistemas casi lineales.${\displaystyle O(n\log \log n)}$tiempo. ^{[ 5 ]} En modelos de computación aún más restringidos, como el árbol de decisión algebraico , el problema puede resolverse en el tiempo algo más lento.${\displaystyle O(n\log n)}$límite de tiempo, ^{[ 6 ]} y esto es óptimo para este modelo, por una reducción del problema de unicidad de elementos . Tanto los algoritmos de barrido lineal como los algoritmos de divide y vencerás con este límite de tiempo más lento se enseñan comúnmente como ejemplos de estas técnicas de diseño de algoritmos. ^{[ 7 ] [ 8 ]}

Un algoritmo aleatorio de tiempo esperado lineal de Rabin (1976) , modificado ligeramente por Richard Lipton para facilitar su análisis, procede de la siguiente manera, sobre un conjunto de entrada${\displaystyle S}$compuesto de${\displaystyle n}$puntos en un${\displaystyle k}$Espacio euclidiano de -dimensiones:

1. Seleccionar${\displaystyle n}$pares de puntos uniformemente al azar, con reemplazo, y sea${\displaystyle d}$sea ​​la distancia mínima de los pares seleccionados.
2. Redondea los puntos de entrada a una cuadrícula cuadrada de puntos cuyo tamaño (la separación entre puntos adyacentes de la cuadrícula) es${\displaystyle d}$y utiliza una tabla hash para agrupar pares de puntos de entrada que se redondean al mismo punto de la cuadrícula.
3. Para cada punto de entrada, calcule la distancia a todas las demás entradas que se redondean al mismo punto de la cuadrícula o a otro punto de la cuadrícula dentro del vecindario de Moore de${\displaystyle 3^{k}-1}$puntos de la cuadrícula circundantes.
4. Devuelve la menor de las distancias calculadas durante este proceso.

El algoritmo siempre determinará correctamente el par más cercano, porque asigna a cualquier par que esté más cerca que la distancia${\displaystyle d}$al mismo punto de la cuadrícula o a puntos adyacentes. El muestreo uniforme de pares en el primer paso del algoritmo (en comparación con un método diferente de Rabin para muestrear un número similar de pares) simplifica la demostración de que el número esperado de distancias calculadas por el algoritmo es lineal. ^{[ 4 ]}

En cambio, un algoritmo diferente, Khuller y Matias (1995), pasa por dos fases: un proceso de filtrado iterativo aleatorio que aproxima la distancia más cercana dentro de una razón de aproximación de${\displaystyle 2{\sqrt {k}}}$, junto con un paso final que convierte esta distancia aproximada en la distancia más cercana exacta. El proceso de filtrado repite los siguientes pasos, hasta${\displaystyle S}$queda vacío:

1. Elige un punto${\displaystyle p}$uniformemente al azar de${\displaystyle S}$.
2. Calcula las distancias desde${\displaystyle p}$a todos los demás puntos de${\displaystyle S}$y dejar${\displaystyle d}$sea ​​la distancia mínima de este tipo.
3. Redondea los puntos de entrada a una cuadrícula cuadrada de tamaño${\displaystyle d/(2{\sqrt {k}})}$y eliminar de${\displaystyle S}$todos los puntos cuyo vecindario de Moore no tiene otros puntos.

La distancia aproximada encontrada por este proceso de filtrado es el valor final de${\displaystyle d}$, calculado en el paso anterior${\displaystyle S}$se vuelve vacío. Cada paso elimina todos los puntos cuyo vecino más cercano está a distancia${\displaystyle d}$o mayor, al menos la mitad de los puntos en expectativa, de lo cual se deduce que el tiempo total esperado para el filtrado es lineal. Una vez que se obtiene un valor aproximado de${\displaystyle d}$Se sabe que puede utilizarse para los pasos finales del algoritmo de Rabin; en estos pasos, cada punto de la cuadrícula tiene un número constante de entradas redondeadas a él, por lo que el tiempo vuelve a ser lineal. ^{[ 3 ]}

La versión dinámica para el problema del par más cercano se plantea de la siguiente manera:

• Dado un conjunto dinámico de objetos, encuentre algoritmos y estructuras de datos para el recálculo eficiente del par de objetos más cercanos cada vez que se inserten o eliminen objetos.

Si se conoce de antemano el cuadro delimitador para todos los puntos y se dispone de la función piso de tiempo constante, entonces se espera${\displaystyle O(n)}$Se sugirió una estructura de datos de espacio que admite el tiempo esperado.${\displaystyle O(\log n)}$inserciones y eliminaciones y tiempo de consulta constante. Cuando se modifica para el modelo de árbol de decisión algebraico, las inserciones y eliminaciones requerirían${\displaystyle O(\log ^{2}n)}$tiempo esperado. ^{[ 9 ]} La complejidad del algoritmo de par más cercano dinámico citado anteriormente es exponencial en la dimensión${\displaystyle d}$y, por lo tanto, dicho algoritmo resulta menos adecuado para problemas de alta dimensionalidad.

Un algoritmo para el problema dinámico del par más cercano en${\displaystyle d}$El espacio dimensional fue desarrollado por Sergey Bespamyatnikh en 1998. ^{[ 10 ]} Los puntos pueden insertarse y eliminarse en${\displaystyle O(\log n)}$tiempo por punto (en el peor de los casos).

• SIG
• Búsqueda del vecino más cercano