Eu preciso encontrar para cada ponto do conjunto de dados todos os seus vizinhos mais próximos. O conjunto de dados contém aprox. 10 milhões de pontos 2D. Os dados estão próximos da grade, mas não formam uma grade precisa ...

Esta opção exclui (na minha opinião) o uso de árvores KD, onde a suposição básica é que nenhum ponto tem as mesmas coordenadas xe coordenadas y.

Preciso de um algoritmo rápido O (n) ou melhor (mas não muito difícil de implementar :-))) para resolver esse problema ... Devido ao fato de o impulso não ser padronizado, não quero usá-lo ...

Obrigado por suas respostas ou exemplos de código ...