Я хотел бы разработать алгоритм поиска по диапазону, который сообщает обо всех точках на заданном расстоянии от точки запроса.
Точки задаются d целочисленными координатами в крошечном диапазоне, скажем, до 6 бит на измерение (диапазон 0..63), при общем количестве битов, не превышающем 60 бит.
Метрика расстояния - манхэттенская или евклидова (на ваше усмотрение), то есть сумма абсолютных или квадратичных разностей координат. В особом случае одного бита на измерение это расстояние Хэмминга.
Может быть до миллиона точек.
Известно ли вам о практической структуре данных, которая поддерживает быстрые запросы, скажем O(Log²(n)+k)
или аналогичные (с пробелом O(n)
) в таких условиях? Также требуется разумное время предварительной обработки (субквадратичное).
k-D
деревья - это первый вариант, но они не используют конечность координат и, я боюсь, плохо работают в больших измерениях.
Особенно интересен случай одного бита на координату. Приветствуются даже частичные решения.