Ответ 1
Если k относительно мало (< 20 или около того), и вы имеете приблизительно равномерное распределение, создайте сетку, которая накладывает диапазон, в котором точки падают, выбирается так, чтобы среднее число точек на сетку было удобно выше, чем k (так что центрально расположенная точка, как правило, получает свои k соседей в этой одной точке сетки). Затем создайте набор других сеток, установленных в половину от первого (перекрывающегося) вдоль каждой оси. Теперь для каждой точки вычислите, к какому элементу сетки он попадает (поскольку сетки являются регулярными, поиск не требуется) и выберите один из четырех (или хотя бы несколько перекрывающихся сеток, которые у вас есть), у которого есть точка, ближайшая к ее центру.
Внутри каждого элемента сетки точки должны сортироваться в одной координате (пусть говорят x). Начиная с выбранного вами элемента (найдите его с помощью деления пополам), выходите наружу по отсортированному списку, пока не найдете k элементов (опять же, если k мало, самый быстрый способ сохранить список лучших хитов - с бинарной сортировкой вставки, позволяя худшему совпадению упасть с конца, когда вы вставляете; сортировка вставки обычно превосходит все остальное до 30 элементов на современном оборудовании). Продолжайте движение, пока ваш самый дальний ближайший сосед не станет ближе к вам, чем следующие точки от вас по x (т.е. Не считая их смещение y, поэтому не может быть новой точки, которая может быть ближе, чем к-к-ближайший, найденный до сих пор).
Если у вас еще нет k очков или у вас есть k точек, но одна или несколько стенок элемента сетки находятся ближе к вашей точке интереса, чем самая дальняя из k точек, добавьте соответствующие соседние элементы сетки в поиск.
Это должно дать вам что-то вроде O(N*k^2) с относительно низким постоянным коэффициентом. Если k велико, то эта стратегия слишком упрощена, и вы должны выбрать алгоритм, линейный или логарифмический по k, например kd-деревья.