Широко ли используется дерево диапазонов в задачах пространственного поиска?

Question

Я ищу некоторые структуры данных для поиска диапазона. Я думаю, что деревья диапазона предлагают хорошую сложность времени (но с некоторыми требованиями к хранению).

Однако мне кажется, что другие структуры данных, такие как KD-деревья, более обсуждаются и рекомендуются, чем деревья диапазонов. Это правда? Если так, то почему?

Answer 1

Я ожидаю, что это потому, что kd-деревья могут быть непосредственно расширены, чтобы содержать объекты, отличные от точек. Это дает ему множество приложений, например, в виртуальных мирах, где мы хотим быстро запрашивать треугольники. Подобные расширения деревьев диапазона не просты, и на самом деле я никогда не видел ни одного.

Чтобы быстро подвести итоги: kd-дерево может предварительно обработать набор из n точек в d-пространстве за O(n log n) времени в структуру, используя O(n) пространство, так что на любой запрос d-мерного диапазона можно ответить за O (n^{1-1 / d} + k) время, где k - количество ответов. Деревья диапазона занимают O (n log^d-1 n) времени для предварительной обработки, занимают O (n log^d-1 n) места и могут отвечать на запросы диапазона за O (log^d-1 n + k) времени.

Время запроса для дерева диапазонов, очевидно, намного лучше, чем для дерева kd, если мы говорим о 2- или 3-мерном пространстве. Однако у kd-дерева есть несколько преимуществ. Прежде всего, это всегда требует только линейного хранения. Во-вторых, он всегда строится за O(n log n) времени. В-третьих, если размерность очень высока, она превзойдет дерево диапазонов, если ваши наборы точек не очень велики (хотя, возможно, в этот момент линейный поиск будет почти таким же быстрым, как и в kd-дереве).

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

РЕДАКТИРОВАТЬ: Вы спрашиваете, какая структура данных лучше для поиска 2D или 3D с фиксированным радиусом, когда у вас есть миллионы точек. Я действительно не могу вам сказать! Я был бы склонен сказать, что дерево диапазонов будет быстрее, если вы выполняете много запросов, но для 3D построение будет медленнее с коэффициентом O(log n), и использование памяти может стать проблемой раньше, чем скорость. Я бы порекомендовал интегрировать хорошие реализации обеих структур и просто протестировать, что лучше подходит для ваших конкретных требований.

Answer 2

Для ваших нужд (моделирование частиц в 2D или 3D) вам нужна структура данных, способная выполнять запросы ближайших соседей. Дерево покрытия - это структура данных, которая лучше всего подходит для этой задачи. Я сталкивался с этим при вычислении ближайших соседей для оценки плотности ядра. Эта страница Википедии объясняет базовое определение дерева, а страница Джона Лэнгфорда содержит ссылку на реализацию C++.

Время выполнения одного запроса - O(c^12*logn), где c - константа раскрытия набора данных. Это верхняя граница - на практике структура данных работает быстрее, чем другие. В этой статье показано, что время выполнения пакетной обработки всех ближайших соседей (для всех точек данных), необходимое для моделирования частиц, равно O(c^16*n), и эта теоретическая линейная граница также полезна для ваших нужд., Время строительства O(nlogn) и хранения O(n).