Problema del par de puntos más cercanos
En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclidiano fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos.[1][2]
Un algoritmo ingenuo para resolver el problema consiste en "calcular las distancias entre todos los pares de puntos del conjunto y seleccionar el mínimo", que requiere un tiempo O(n^2). Pero resulta que el problema puede ser solucionado en tiempo O(n log n) en un espacio euclídeo.[3] Este tiempo puede incluso ser mejorado: Si asumimos que la función de parte entera (floor) es computable en tiempo constante, el problema puede ser solucionado en tiempo O(n log log n).[4] Si además permitimos utilizar aleatorización, el problema puede ser solucionado en tiempo O(n).[5][6]
Algoritmo de fuerza bruta
El par más cercano de puntos puede ser encontrado en tiempo proporcional a O(n^2) mediante una búsqueda por fuerza bruta. Para ello habría que computar las distancias entre las combinaciones de pares de puntos, y elegir el par con la distancia más pequeña.
minDist = infinito para i = 1 a longitud(P) - 1 para j = i + 1 a longitud(P) dist = distancia(P[i], P[j]) si dist < minDist: minDist = dist closestPair = (i, j) devolver closestPair
Algoritmo recursivo en el plano 2D
El problema puede ser resuelto en tiempo O(n log n) usando un algoritmo recursivo tipo divide y vencerás, p. ej., como sigue:
- Ordenar los puntos según su coordenada X.
- Si el tamaño del conjunto es 2, devolver la distancia entre ellos. Si el conjunto tiene 0 o 1 elementos, devolver infinito.
- Dividir el conjunto de puntos en dos partes iguales (del mismo número de puntos).
- Solucionar el problema de forma recursiva en las partes izquierdas y derecha. Esto devolverá una solución para cada parte, llamadas dLmin y dRmin. Escoger el mínimo entre estas dos soluciones, llamado dLRmin.
- Seleccionar los puntos de la parte derecha e izquierda que están a una distancia horizontal menor que dLRmin de la recta divisoria entre ambos. Aprovechar que los puntos están ordenados para elegir los últimos puntos de la parte izquierda y los primeros de la parte derecha.
- Encontrar la distancia mínima dCmin entre todos los pares de puntos formados por un punto de cada parte del paso anterior.
- La respuesta final es el mínimo entre dCmin y dLRmin.
Resulta que el paso 6 puede ser cumplido en tiempo lineal. De nuevo, un algoritmo ingenuo requeriría el cálculo de distancias para todos los pares izquierdos-derechos, usando tiempo cuadrático. La clave está en que sabemos que la distancia del par de puntos más cercano no debe ser mayor que dLRmin=min(dLmin, dRmin), por tanto, para cada punto a la izquierda de la línea divisoria sólo tenemos que comparar las distancias a los puntos de la parte derecha dentro del rectángulo de dimensiones (dist, 2 ⋅ dist). Además, este rectángulo puede contener como máximo ocho puntos con distancias iguales o menores a dLRmin (de no ser así, dLRmin debería haber tomado un valor más bajo). Por tanto, es suficiente calcular como máximo 7 distancias en dicho paso.[7] La relación de recurrencia para el número de pasos es T(n) = 2 T(n/2) + O(n), y podemos utilizar el teorema maestro para calcular que el orden total es O(n log n).
Solución mediante triangulación de Delaunay
Otra forma de resolver el problema del par más cercano es aprovechar la propiedad de la triangulación de Delaunay que indica que «cada vértice de la triangulación siempre estará conectado con su vértice más cercano». Por lo tanto, el par de puntos más cercano puede ser determinado en tiempo lineal cuando disponemos de la triangulación de Delaunay (o el diagrama de Voronoi) calculando las longitudes de las aristas. Como el cálculo de la triangulación de Delaunay toma tiempo O(n log n), este proceso domina sobre el tiempo en encontrar la arista más corta, y a su vez sirve de cota al tiempo necesario para encontrar el par más cercano.
Referencias y enlaces externos
- Shamos, Michael; Hoey, Dan (1975). . Proceedings of the 16th Annual Symposium on Foundations of Computer Science: 151-162. doi:10.1109/SFCS.1975.8. Archivado desde el original el 3 de marzo de 2017. Consultado el 3 de marzo de 2017.
- Franco P. Preparata y Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
- Clarkson, Kenneth (1983). «Fast algorithms for the all nearest neighbors problem». Proceedings of the 24th Annual Symposium on Foundations of Computer Science: 226-232 =. doi:10.1109/SFCS.1983.16.
- Fortune, S.; Hopcroft, J.E. (1979). «A note on Rabin's nearest-neighbor algorithm». Information Processing Letters 8 (1): 20-23.
- Khuller, Samir; Matias, Yossi (1995). A simple Randomized Sieve Algorithm for the Closest-Pair problem.
- Richard Lipton (24 de septiembre de 2011). «Rabin Flips a Coin».
- Cormen; Leiserson; Rivest; Stein (2001). . Introduction to Algorithms. MIT Press. pp. 957-966. ISBN 9780262259460. Archivado desde el original el 23 de septiembre de 2014. Consultado el 3 de marzo de 2017.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 957–961 of section 33.4: Finding the closest pair of points.
- Jon Kleinberg; Éva Tardos (2006). Algorithm Design. Addison Wesley.
- UCSB Lecture Notes on "Closest Pair Problem"
- rosettacode.org - "Closest pair of points" implementado en varios lenguajes de programación.
- Line sweep algorithm for the closest pair problem