El problema del par de puntos más cercano o el problema del par más cercano es un problema de geometría computacional : dados n puntos 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.
Un algoritmo ingenuo para encontrar distancias entre todos los pares de puntos en un espacio de dimensión dy seleccionar el mínimo requiere O ( n 2 ) tiempo. Resulta que el problema puede resolverse en O ( n log n ) tiempo en un espacio euclidiano o L p espacio de dimensión fija d. [2] En el modelo de cálculo de árbol de decisión algebraico , el algoritmo O ( n log n ) es óptimo, mediante una reducción del problema de unicidad del elemento. En el modelo computacional que asume que la función piso es computable en tiempo constante, el problema se puede resolver en O ( n log log n ) tiempo. [3] Si permitimos que se use la aleatorización junto con la función de piso, el problema se puede resolver en O ( n ) tiempo. [4] [5]
Problema dinámico del par más cercano
La versión dinámica para el problema del par más cercano se indica a continuación:
- Dado un conjunto dinámico de objetos, busque algoritmos y estructuras de datos para un cálculo eficiente del par de objetos más cercano cada vez que se insertan o eliminan.
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 O ( n ) esperada que admite inserciones y eliminaciones de O (log n ) 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 un tiempo esperado de O (log 2 n ). [6] Sin embargo, vale la pena señalar que la complejidad del algoritmo de par dinámico más cercano citado anteriormente es exponencial en la dimensión d , y por lo tanto, dicho algoritmo se vuelve menos adecuado para problemas de alta dimensión.
Un algoritmo para la dinámica problema más cercano pair en d espacio dimensional fue desarrollado por Sergey Bespamyatnikh en 1998. [7] Los puntos pueden ser insertados y eliminan en O (log n tiempo) por cada punto (en el peor de los casos).
Ver también
Notas
- ^ MI Shamos y D. Hoey . "Problemas más cercanos". En Proc. 16 ° Simposio anual del IEEE sobre fundamentos de la informática (FOCS), págs. 151-162, 1975 (DOI 10.1109 / SFCS.1975.8 )
- ^ KL Clarkson, "Algoritmos rápidos para el problema de todos los vecinos más cercanos", FOCS 1983.
- ^ S. Fortune y JE Hopcroft. "Una nota sobre el algoritmo del vecino más cercano de Rabin". Information Processing Letters, 8 (1), págs. 20 a 23, 1979
- ^ S. Khuller e Y. Matias. Un algoritmo de tamiz aleatorio simple para el problema del par más cercano. Inf. Computación., 118 (1): 34—37,1995
- ^ Richard Lipton (24 de septiembre de 2011). "Rabin lanza una moneda" .
- ^ Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid, "Estructuras de datos aleatorias para el problema dinámico del par más cercano", SIAM J. Comput. , vo. 27, no. 4, 1998, versión preliminar informada en el IV Annu. ACM-SIAM Symp. sobre algoritmos discretos, págs. 301–310 (1993)
- ^ Sergey Bespamyatnikh, Un algoritmo óptimo para el mantenimiento del par más cercano. Computación discreta. Geom. 19: 175-195, 1998.
Referencias
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Páginas 957–961 de la sección 33.4: Encontrar el par de puntos más cercano.
- Jon Kleinberg; Éva Tardos (2006). Diseño de algoritmos . Addison Wesley.CS1 maint: varios nombres: lista de autores ( enlace )
- Notas de la conferencia de Subhash Suri
- rosettacode.org : el par de puntos más cercano implementado en varios lenguajes de programación
- Algoritmo de barrido de línea para el problema de par más cercano