Похожий вопрос:

https://gamedev.stackexchange.com/q/87138/144672

Добрый вечер! Есть какая-нибудь годная книга по алгоритмам?

Да. Кормен

Топ, как раз по теме - спасибо

Если задача состоит в том, чтобы найти ближайших соседей для одной точки/объекта, то можно  просто пробегать по списку с координатами всех объектов, вычисляя расстояние от целевой точки до каждого. Сложность O(n). И деревья не нужны.

Зелёная точка целевая, красные находятся от неё на расстоянии k, синие дальше.

Вот такой скриптик на Python написал:

import matplotlib.pyplot as plt
import random
from math import sqrt

def draw_points(target_x, target_y, x_lst, y_lst, distance):
    for x, y in zip(x_lst, y_lst):
        # Pythagorean theorem
        a = abs(target_x - x)
        b = abs(target_y - y)
        c = sqrt(a**2 + b**2)

        color = "blue"
        if c < distance:
            color = "red"

        plt.plot(x, y, 'o', color=color)

# Случайные числа зафиксированны для воспроизводимости графика.
# Закомментировать или удалить для генерации разных чисел.
random.seed(196008)

x_lst = [random.randint(1, 100) for _ in range(20)]
y_lst = [random.randint(1, 100) for _ in range(20)]

target_point_x, target_point_y = random.randint(1, 100), random.randint(1, 100)

plt.plot(target_point_x, target_point_y, 'go', markersize=10)
draw_points(target_point_x, target_point_y, x_lst, y_lst, 40)

plt.show()

перепроверил условие - k ближайших соседей. целевая точка не меняется, множество точек может изменяться, так?

Изначально была задача, что все точки меняют координаты чаще чем делается запрос на ближайших соседей. И тип как это реализовать для хотя бы 1к эллементов.

Тип динамическое множество точек.

Потом былы другие обсуждения...

Если задача практическая, то не хватает ещё очень много контекста

Распределение точек, как часто запросы, насколько большие координаты, на чём это все будет раниться

Если 1к элементов и если апдейты заметно чаще запросов, то вариации наивных решений могут быть очень даже ничего

Да, я решил не усложнять со структурой данных, и остановился на мапе.

В итоге использую ConcurrentHashMap с тредпулом от 2 до 10 потоков, время idle потока 120 секунд до удаления.

Решил брать либо одного ближайшего либо всех в радиусе

1. O(log n) конечно лучше, чем O(n), кто спорит.
2. O(log n) это для нахождения одного соседа, а если задать k = "максимально возможное расстояние", то искать надо будет n элементов.
3. Дерево ещё и строить надо или обновлять. Если элементы меняются часто и помногу, то выгоднее каждый раз строить дерево заново. А построить дерево для 10 000 элементов явно дольше, чем просто пробежать по 10 000 элементам.

а какие n и k?

n ~ 1к, k < 10

быстрее всего цикл, конечно же. Вплоть до k == 20-30k

если учесть частоту обновления, то k ещё может быть в разы больше