Problema del par de puntos más cercano
El problema del par de puntos más cercano o el problema del par más cercano es un problema de geometría computacional : puntos dados en el espacio métrico , encuentre un par de puntos con la menor distancia entre ellos. El problema de pares 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 a los efectos del análisis asintótico . [2] [3] [4] Esto es significativamente más rápido que el 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 el más pequeño.
También es posible resolver el problema sin aleatorización, en modelos de computación de máquina de acceso aleatorio con memoria ilimitada que permiten el uso de la función de piso , en tiempo casi lineal . [5] En modelos de cálculo aún más restringidos, como el árbol de decisión algebraico , el problema se puede resolver en un límite de tiempo algo más lento , [6] y esto es óptimo para este modelo, mediante una reducción del problema de unicidad de elementos . Ambos algoritmos línea de barrido y algoritmos divide y vencerás con este tiempo más lento unido se enseñan comúnmente como ejemplos de estas técnicas de diseño de algoritmo.[7] [8]
Un algoritmo aleatorio de tiempo lineal esperado de Rabin (1976) , modificado ligeramente por Richard Lipton para facilitar su análisis, procede de la siguiente manera, en un conjunto de entrada que consta de puntos en un espacio euclidiano -dimensional:
El algoritmo siempre determinará correctamente el par más cercano, porque mapea cualquier par más cercano que la distancia al mismo punto de cuadrícula o puntos de cuadrícula 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 prueba de que el número esperado de distancias calculadas por el algoritmo es lineal. [4]
En cambio, un algoritmo diferente de Khuller y Matias (1995) pasa por dos fases: un proceso de filtrado iterado aleatorio que se aproxima a la distancia más cercana dentro de una relación de aproximación de , 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 que quede vacío:
