Problema del par de puntos más cercanos

[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).

[4]​ Si además se permite utilizar aleatorización, el problema puede ser solucionado en tiempo O(n).

[5]​[6]​ El par más cercano de puntos puede ser encontrado en tiempo proporcional a O(n^2) mediante una búsqueda por fuerza bruta.

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).