Какую структуру данных выбрать для поиска по ортогональному диапазону?
Мне нужно решить задачу поиска соседей, то есть для каждого данного элемента найти все соседние элементы на фиксированном расстоянии.
Я только что узнал структуру данных range treeПохоже, что она способна решить эту проблему в сложности O(N*(log(N)^(d-1))), где d является тусклым пространством.
Я ничего не знаю о R-tree, но только что увидел это из википедии:
Обычное использование R-дерева в реальном мире может состоять в том, чтобы.... затем быстро найти ответы на такие вопросы, как "Найти все музеи в пределах 2 км от моего текущего местоположения",
которая кажется именно той проблемой, которую я хочу решить.
Так что я должен изучить и использовать эту структуру данных？