Estado del arte para el problema de los $K$ vecinos más cercanos

Pravin M. Vaidya [VAnl89]. Este algoritmo resuelve el problema de los $K$ vecinos más cercanos. Es un algoritmo para espacios vectoriales el cual tiene una complejidad de $O(\log n)$, y es muy sensible a la dimensión.

Kenneth L. Clarkson [Cla83]. Es un algoritmo para espacios métricos que soluciona el problema de todos los vecinos más cercanos en $O(n \log \sigma)$ tiempo, donde $\sigma$ es el radio de la distancia entre el par de puntos más lejanos a la distancia entre el par de puntos más cercanos. Este algoritmo construye un celltree, una compresión de un trie digital, en $O(n \log n)$ tiempo probabilístico, finalmente su complejidad es $O(n(\log n)^2(\log \eta)^2))$ donde $\eta$ es la constante de empacamiento.