У меня есть N точек, которые лежат только на вершинах куба, размерности D, где D - что-то вроде 3.

Вершина может не содержать никакой точки. Таким образом, каждая точка имеет координаты в {0, 1}D. Меня интересует только время запроса, если стоимость памяти разумна (не экспоненциально в N, например :)).

Предоставить запрос, который лежит на одной из вершин куба и входной параметрr, найдите все вершины (то есть точки), которые имеют расстояние Хемминга <=r с запросом.

Какой способ пойти вc ++ среда

Я думаю о kd-дереве, но я не уверен и хочу помочь, любой вход, даже приблизительный, будет оценен! Поскольку расстояние Хемминга вступает в игру, битовые манипуляции должны помочь (например, XOR).