Encontrando todos los $K$ vecinos más cercanos

Dada un conjunto de puntos $U$, tal que , en un espacio métrico, se desea conocer para cada elemento () sus $K$ vecinos más cercanos. La complejidad del problema se mide en cálculos de distancia; se sabe que usando la fuerza bruta el problema es resuelto en $n^2$ cálculos de distancia.

En esta sección se planteará el desarrollo del algoritmo, el cual consiste en indexar la base de datos en tiempo lineal, después, hacer $n$ consultas de rango con un radio seguro para conocer los $K$ vecinos más cercanos, donde un radio seguro es aquel que contiene al menos $K$ vecinos más cercanos; esta heurística se puede mejorar con una estructura auxiliar llamada heap ó cola de prioridad, en la cual se mantienen al menos $K$ elementos más cercanos para cada punto durante el desarrollo del algoritmo, con esta estructura se pretende reducir los radios de cada punto cada vez que se pueda.