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