Problema del par de puntos más cercano

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 , encuentra un par de puntos con la distancia más pequeña 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 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 para 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 acceso aleatorio con memoria ilimitada que permiten el uso de la función 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 del elemento . 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 en tiempo lineal

Un algoritmo aleatorio lineal de tiempo esperado de Rabin (1976), ligeramente modificado 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 de dimensión: ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle k}$

1. Seleccione pares de puntos uniformemente 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 la cuadrícula adyacentes) sea , y use una tabla hash para reunir pares de puntos de entrada que se redondean al mismo punto de la 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 de la vecindad de Moore de los puntos de la cuadrícula circundantes. ${\displaystyle 3^{k}-1}$
4. Devuelve la más pequeña 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 la 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 y Matias (1995), pasa por dos fases: un proceso de filtrado iterado aleatorio que aproxima 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: ${\displaystyle 2{\sqrt {k}}}$ ${\displaystyle S}$

1. Elija un punto uniformemente al azar de . ${\displaystyle p}$ ${\displaystyle S}$
2. Calcule las distancias desde hasta 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 cuya vecindad 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 antes de quedar 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, 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 para el problema del par más cercano se expresa de la siguiente manera:

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

Si el cuadro delimitador para todos los puntos se conoce de antemano y la función mínima 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 el tiempo esperado. ^[9] La complejidad del algoritmo dinámico del par más cercano 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ó un algoritmo para el problema dinámico del par más cercano en el espacio dimensional en 1998. ^[10] Los puntos se pueden insertar y eliminar en el tiempo por punto (en el peor de los casos). ${\displaystyle d}$ ${\displaystyle O(\log n)}$

Ver también

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

Notas

1. Shamos, Michael Ian ; Hoey, Dan (1975). "Problemas del punto más cercano". 16º Simposio Anual sobre Fundamentos de la Informática, Berkeley, California, EE.UU., 13 al 15 de octubre de 1975 . Sociedad de Computación IEEE. 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 . Prensa académica. págs. 21–39.Según lo citado por Khuller y Matías (1995).
3. Khuller, Samir ; Matías, Yossi (1995). "Un algoritmo de tamiz aleatorio simple para el problema del par más cercano". Información y Computación . 118 (1): 34–37. doi : 10.1006/inco.1995.1049 . SEÑOR  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. Fortuna, Steve; Hopcroft, John (1979). "Una nota sobre el algoritmo del vecino más cercano de Rabin". Cartas de procesamiento de información . 8 (1): 20–23. doi :10.1016/0020-0190(79)90085-1. hdl : 1813/7460 . SEÑOR  0515507.
6. Clarkson, Kenneth L. (1983). "Algoritmos rápidos para el problema de todos los vecinos más cercanos". 24º Simposio anual sobre fundamentos de la informática, Tucson, Arizona, EE. UU., 7 al 9 de noviembre de 1983 . Sociedad de Computación IEEE. 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". Diseño de algoritmos . Addison-Wesley. págs. 225-231. ISBN 978-0-321-37291-8.
9. Golin, Mardoqueo; Raman, Rajeev; Schwarz, cristiano; Smid, Michiel (1998). "Estructuras de datos aleatorias para el problema dinámico del par más cercano" (PDF) . Revista SIAM de Computación . 27 (4): 1036–1072. doi :10.1137/S0097539794277718. SEÑOR  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 . SEÑOR  1600047.