Problema del par de puntos más cercano

El par más cercano problema de puntos o problema pareja más cercano es un problema de la geometría computacional: dado ${\displaystyle n}$ puntos en el espacio métrico, encontrar un par de puntos con la distancia más pequeña entre ellos. El problema de par más cercano para puntos en el plano Euclidean fue uno de los primeros problemas geométricos que fueron tratados en los orígenes del estudio sistemático de la complejidad computacional de los algoritmos geométricos.

Los algoritmos aleatorios que resuelven el problema en tiempo lineal son conocidos, en espacios euclidianos cuya dimensión se trata como una constante para los fines del análisis asintotico. Esto es significativamente más rápido que el ${\displaystyle O(n^{2}}$ tiempo (expresado aquí en gran notación O) que sería obtenido por 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 máquina de acceso aleatorio de computación con memoria ilimitada que permiten el uso de la función del suelo, en línea cercana ${\displaystyle O(n\log \log n)}$ tiempo. En modelos aún más restringidos de computación, como el árbol de decisión algebraica, el problema se puede resolver en el algo más lento ${\displaystyle O(n\log n)}$ tiempo límite, y esto es óptimo para este modelo, por una reducción del problema de la singularidad del elemento. Tanto algoritmos de línea de barrido como algoritmos de división y conquista con este tiempo más lento se enseñan comúnmente como ejemplos de estas técnicas de diseño del algoritmo.

Un algoritmo aleatorizado de tiempo esperado lineal de Rabin (1976), modificado ligeramente por Richard Lipton para facilitar su análisis, procede como sigue, en un conjunto de entrada ${\displaystyle S.$ consistente en ${\displaystyle n}$ puntos en un ${\displaystyle k}$-dimensional Espacio euclidiano:

1. Seleccione ${\displaystyle n}$ pares de puntos uniformemente al azar, con reemplazo, y dejar ${\displaystyle d}$ ser la distancia mínima de los pares seleccionados.
2. Redondear los puntos de entrada a una rejilla cuadrada de puntos cuyo tamaño (la separación entre puntos de rejilla adyacentes) es ${\displaystyle d}$, y utilizar una tabla de hash para reunir pares de puntos de entrada que rondan al mismo punto de rejilla.
3. Para cada punto de entrada, computar la distancia a todas las entradas que redondeen al mismo punto de rejilla o a otro punto de rejilla dentro del barrio de Moore ${\displaystyle 3^{k}-1}$ puntos de rejilla circundantes.
4. Devuelve las distancias más pequeñas calculadas a lo largo de este proceso.

El algoritmo siempre determinará correctamente el par más cercano, porque mapea cualquier par más cerca que la distancia ${\displaystyle d}$ al mismo punto de rejilla o a puntos de rejilla 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 computadas por el algoritmo es lineal.

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

1. Elige un punto ${\displaystyle p}$ uniformemente al azar ${\displaystyle S.$.
2. Computar las distancias desde ${\displaystyle p}$ a todos los demás puntos ${\displaystyle S.$ y dejar ${\displaystyle d}$ ser el mínimo de tal distancia.
3. Redondear 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 barrio de Moore no tiene otros puntos.

La distancia aproximada encontrada por este proceso de filtrado es el valor final de ${\displaystyle d}$, computado 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 espera, de los cuales sigue que el tiempo total esperado para el filtrado es lineal. Una vez un valor aproximado ${\displaystyle d}$ es conocido, se puede utilizar para los pasos finales del algoritmo de Rabin; en estos pasos cada punto de rejilla tiene un número constante de entradas redondeadas a él, así que de nuevo el tiempo es lineal.

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

• Dado un conjunto dinámico de objetos, encontrar algoritmos y estructuras de datos para la recalculación eficiente del par más cercano de objetos cada vez que se insertan o eliminan los objetos.

Si la caja de fijación para todos los puntos es conocida por adelantado y la función de suelo de tiempo constante está disponible, entonces la espera ${\displaystyle O(n)}$- Se sugirió que la estructura de datos espaciales apoyaba el tiempo previsto ${\displaystyle O(\log n)}$ inserciones y eliminaciones y tiempo de consulta constante. Cuando se modifique para el modelo de árbol de decisión algebraico, las inserciones y eliminaciones requerirían ${\displaystyle O(\log ^{2}n)}$ Tiempo esperado. La complejidad del algoritmo de par más dinámico citado anteriormente es exponencial en la dimensión ${\displaystyle d}$, y por lo tanto tal algoritmo se hace menos adecuado para problemas de alta dimensión.

Un algoritmo para el problema de pago más dinámico en ${\displaystyle d}$ dimensional space was developed by Sergey Bespamyatnikh in 1998. Se pueden insertar y eliminar puntos en ${\displaystyle O(\log n)}$ tiempo por punto (en el peor caso).

• GIS
• Búsqueda más cercana