Problema del par de puntos más cercano

Problema de geometría computacional

El par de puntos más cercano se muestra en rojo

El problema del par de puntos más cercano o problema del par más cercano es un problema de geometría computacional : dados 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] estuvo entre 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. ${\displaystyle n}$

Límites de tiempo

Se conocen algoritmos aleatorios que resuelven el problema en tiempo lineal , en espacios euclidianos cuya dimensión se trata como una constante para fines de 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. ${\displaystyle O(n^{2})}$

También es posible resolver el problema sin aleatorización, en modelos de computación de máquinas de acceso aleatorio con memoria ilimitada que permiten el uso de la función de piso , en un tiempo casi lineal . ^[5] En modelos de computación 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 . Tanto los algoritmos de línea de barrido 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]} ${\displaystyle O(n\log \log n)}$ ${\displaystyle O(n\log n)}$

Algoritmos aleatorios de tiempo lineal

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

1. Seleccione pares de puntos de manera uniforme al azar, con reemplazo, y sea la distancia mínima de los pares seleccionados. ${\displaystyle n}$ ${\displaystyle d}$
2. Redondee los puntos de entrada a una cuadrícula cuadrada de puntos cuyo tamaño (la separación entre puntos de cuadrícula adyacentes) sea , y utilice una tabla hash para recopilar pares de puntos de entrada que se redondeen al mismo punto de cuadrícula. ${\displaystyle d}$
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 los puntos de la cuadrícula circundantes. ${\displaystyle 3^{k}-1}$
4. Devuelve la menor de las distancias calculadas a lo largo de este proceso.

El algoritmo siempre determinará correctamente el par más cercano, porque asigna cualquier par más cercano que la distancia al mismo punto de la cuadrícula o a 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] ${\displaystyle d}$

En cambio, un algoritmo diferente, Khuller & Matias (1995), pasa por dos fases: un proceso de filtrado iterativo aleatorio que aproxima la distancia más cercana a dentro de una razó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 se vacía: ${\displaystyle 2{\sqrt {k}}}$ ${\displaystyle S}$

1. Elija un punto uniformemente al azar de . ${\displaystyle p}$ ${\displaystyle S}$
2. Calcular las distancias desde a todos los demás puntos de y sea la distancia mínima. ${\displaystyle p}$ ${\displaystyle S}$ ${\displaystyle d}$
3. Redondee los puntos de entrada a una cuadrícula de tamaño y elimine todos los puntos cuyo vecindario de Moore no tenga otros puntos. ${\displaystyle d/(2{\sqrt {k}})}$ ${\displaystyle S}$

La distancia aproximada encontrada por este proceso de filtrado es el valor final de , calculado en el paso anterior a que quede vacío. Cada paso elimina todos los puntos cuyo vecino más cercano esté a una distancia o mayor, al menos la mitad de los puntos esperados, de lo que se deduce que el tiempo total esperado para el filtrado es lineal. Una vez que se conoce un valor aproximado de , se puede utilizar 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 nuevamente el tiempo es lineal. ^[3] ${\displaystyle d}$ ${\displaystyle S}$ ${\displaystyle d}$ ${\displaystyle d}$

Problema dinámico del par más cercano

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, encuentre algoritmos y estructuras de datos para el recálculo eficiente del par de objetos más cercano cada vez que se inserten o eliminen los objetos.

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

Sergey Bespamyatnikh desarrolló en 1998 un algoritmo para el problema dinámico del par más cercano en el espacio dimensional. ^[10] Se pueden insertar y eliminar puntos a tiempo por punto (en el peor de los casos). ${\displaystyle d}$ ${\displaystyle O(\log n)}$

Véase también

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

Notas

1. Shamos, Michael Ian ; Hoey, Dan (1975). "Closest-point problems". 16.º Simposio anual sobre fundamentos de la informática, Berkeley, California, EE. UU., 13-15 de octubre de 1975 . IEEE Computer Society. págs. 151–162. doi :10.1109/SFCS.1975.8.
2. Rabin, M. (1976). "Algoritmos probabilísticos". Algoritmos y complejidad: resultados recientes y nuevas direcciones . Academic Press. págs. 21–39.Como citan Khuller y Matias (1995).
3. Khuller, Samir ; Matias, Yossi (1995). "Un algoritmo de criba aleatorizado simple para el problema del par más cercano". Información y computación . 118 (1): 34–37. doi : 10.1006/inco.1995.1049 . MR  1329236. S2CID  206566076.
4. Lipton, Richard (24 de septiembre de 2011). "Rabin lanza una moneda". La carta perdida de Gödel y P=NP .
5. Fortune, Steve; Hopcroft, John (1979). "Una nota sobre el algoritmo del vecino más próximo de Rabin". Cartas de procesamiento de la información . 8 (1): 20–23. doi :10.1016/0020-0190(79)90085-1. hdl : 1813/7460 . MR  0515507.
6. Clarkson, Kenneth L. (1983). "Algoritmos rápidos para el problema de todos los vecinos más próximos". 24.º Simposio anual sobre fundamentos de la informática, Tucson, Arizona, EE. UU., 7-9 de noviembre de 1983. IEEE Computer Society. págs. 226–232. doi :10.1109/SFCS.1983.16.
7. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "33.4: Encontrar el par de puntos más cercano". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 957–961. ISBN 0-262-03293-7.
8. Kleinberg, Jon M. ; Tardos, Éva (2006). "5.4 Encontrar el par de puntos más cercano". Algorithm Design . Addison-Wesley. págs. 225–231. ISBN 978-0-321-37291-8.
9. Golin, Mordecai; Raman, Rajeev; Schwarz, Christian; Smid, Michiel (1998). "Estructuras de datos aleatorizadas para el problema dinámico del par más cercano" (PDF) . SIAM Journal on Computing . 27 (4): 1036–1072. doi :10.1137/S0097539794277718. MR  1622005. S2CID  1242364.
10. Bespamyatnikh, SN (1998). "Un algoritmo óptimo para el mantenimiento del par más cercano". Geometría discreta y computacional . 19 (2): 175–195. doi : 10.1007/PL00009340 . MR  1600047.