Для n точек в d-мерном пространстве существует несколько структур данных, таких как Kd-Trees, Quadtrees и т. Д. Для индексации точек. На этих структурах данных можно реализовать прямой алгоритм для запросов ближайшего соседа вокруг заданной входной точки. Есть ли книга, статья, опрос ..., в которой сравнивается теоретическая (в основном ожидаемая) среда выполнения запроса ближайшего соседа для разных структур данных? Данные, на которые я смотрю, состоят из довольно маленьких облаков точек, поэтому все они могут быть обработаны в основной памяти. Для простоты я предполагаю, что данные распределены равномерно. То есть меня не интересует реальная производительность, а скорее теоретические результаты