Пространственное разбиение - это фактически семейство тесно связанных алгоритмов, которые разделяют пространство, чтобы приложения могли легче обрабатывать точки или многоугольники.
Я считаю, что есть много способов решить вашу проблему. Я не знаю, насколько сложным вы готовы построить свое решение. Простой способ, вероятно, построить двоичное дерево, разделяющее пространство на 2. Все точки разделены между некоторой средней плоскостью. Постройте свое дерево путем рекурсивного деления, пока у вас не кончатся точки.
Поиск ближайшего соседа будет оптимизирован, поскольку каждый обход дерева сужает область поиска.
В некоторой литературе они называют это кД-деревом