ужно найти для каждой точки набора данных всех своих ближайших соседей. Набор данных содержит ок. 10 миллионов 2D очков. Данные близки к сетке, но не образуют точную сетку ...

Эта опция исключает (на мой взгляд) использование деревьев KD, где основное предположение состоит в том, что точки не имеют одинаковую координату x и координату y.

Мне нужен быстрый алгоритм O (n) или лучше (но не слишком сложный для реализации :-))), чтобы решить эту проблему ... Из-за того, что boost не стандартизирован, я не хочу его использовать ...

Спасибо за ваши ответы или примеры кода ...