Dados n pontos no espaço d-dimensional, existem várias estruturas de dados, como Kd-Trees, Quadtrees etc. para indexar os pontos. Nessas estruturas de dados, é possível implementar o algoritmo direto para consultas de vizinhos mais próximos em torno de um determinado ponto de entrada. Existe um livro, artigo, pesquisa ... que compara o tempo de execução teórico (geralmente esperado) da consulta de vizinho mais próximo em diferentes estruturas de dados? Os dados que eu estou vendo são compostos de nuvens de pontos bastante pequenas, para que todos possam ser processados na memória principal. Por uma questão de simplicidade, presumo que os dados sejam distribuídos uniformemente. Ou seja, não estou interessado em desempenho do mundo real, mas em resultados teóricos