Ir al contenido

Problema del par de puntos más cercanos

De Wikipedia, la enciclopedia libre
Un conjunto de puntos y su par más cercano en rojo

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 euclídeo 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 se asume 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 se permite utilizar aleatorización, el problema puede ser solucionado en tiempo O(n).[5]​[6]​

Algoritmo de fuerza bruta

[editar]

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

[editar]
Esquema Divide y vencerás: selección de puntos a una distancia de la recta divisoria

El problema puede ser resuelto en tiempo O(n log n) usando un algoritmo recursivo  tipo divide y vencerás, p. ej., como sigue:

  1. Ordenar los puntos según su coordenada X.
  2. Si el tamaño del conjunto es 2, devolver la distancia entre ellos. Si el conjunto tiene 0 o 1 elementos, devolver infinito.
  3. Dividir el conjunto de puntos en dos partes iguales (del mismo número de puntos).
  4. 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.
  5. 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.
  6. Encontrar la distancia mínima dCmin entre todos los pares de puntos formados por un punto de cada parte del paso anterior.
  7. 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 se sabe 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 solo se tienen 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 se puede utilizar el teorema maestro para calcular que el orden total es O(n log n).

Solución mediante triangulación de Delaunay

[editar]

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 se dispone 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

[editar]
  1. ↑ Shamos, Michael; Hoey, Dan (1975). «Closest-point problems». 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. 
  2. ↑ 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. 
  3. ↑ 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. 
  4. ↑ Fortune, S.; Hopcroft, J.E. (1979). «A note on Rabin's nearest-neighbor algorithm». Information Processing Letters 8 (1): 20-23. 
  5. ↑ Khuller, Samir; Matias, Yossi (1995). A simple Randomized Sieve Algorithm for the Closest-Pair problem. 
  6. ↑ Richard Lipton (24 de septiembre de 2011). «Rabin Flips a Coin». 
  7. ↑ Cormen; Leiserson; Rivest; Stein (2001). «33. Computational Geometry». 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. 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Problema_del_par_de_puntos_más_cercanos&oldid=148345405»