Tengo N puntos que se encuentran solo en los vértices de un cubo, de dimensión D, donde D es algo así como 3.

Un vértice no puede contener ningún punto. Entonces cada punto tiene coordenadas en {0, 1}D. Solo estoy interesado enTiempo de consult, siempre que el costo de la memoria sea razonable (no exponencial en N, por ejemplo :)).

Dado una consulta que se encuentra en uno de los vértices del cubo y un parámetro de entradar, encuentre todos los vértices (por lo tanto, puntos) que tienenhamming distance <=r con la consulta.

¿Cuál es el camino a seguir en unac ++ ¿medio ambiente

Estoy pensando en un árbol kd, pero no estoy seguro y quiero ayuda, ¡cualquier aportación, incluso aproximada, sería apreciada! Ya quehamming distance entra en juego, las manipulaciones bit a bit deberían ayudar (por ejemplo, XOR).