Подходящий выбор структуры данных и алгоритма для быстрого поиска k-ближайшего соседа в 2D

У меня есть набор данных примерно из 100 000 пар (X, Y), представляющих точки в 2D-пространстве. Для каждой точки я хочу найти ее k-ближайших соседей.

Итак, мой вопрос - какая структура данных / алгоритм будет подходящим выбором, если я хочу полностью минимизировать общий запуск время?

Я не ищу код - просто указатель на подходящий подход. Меня немного пугает диапазон вариантов, которые кажутся подходящими - квад-деревья, R-деревья, kd-деревья и т. Д.

I ' Я считаю, что лучший подход - построить структуру данных, а затем выполнить какой-то поиск k-ближайшего соседа для каждой точки. Однако, поскольку (а) я знаю точки заранее и (б) я знаю, что должен выполнить поиск каждой точки ровно один раз, возможно, есть лучший подход?

Некоторые дополнительные сведения:

• Поскольку я хочу Чтобы свести к минимуму все время выполнения, меня не волнует, тратится ли большая часть времени на поиск или структуру.
• Пары (X, Y) довольно хорошо распределены, поэтому мы можем предположить почти равномерное распределение.