В чем основное различие между деревом квадрантов и kd-деревом? Я понимаю, что они разделяют точки во многих измерениях, но я не понимаю, почему мы должны использовать одно вместо другого. Мне нужна структура, которая позволяет мне подсчитать, сколько точек (двухмерных точек) находится в данной области. В основном, я пытаюсь обнаружить кластеры точек.
Разница между quadtree и kd-tree
comment
См. также cstheory.stackexchange.com/questions/8470/
- person naught101 schedule 21.03.2014
Ответы (1)
Разница (алгоритмически) заключается в следующем: в деревьях квадрантов данные, достигающие узла, разбиваются на фиксированные (2 ^ d) ячейки одинакового размера, тогда как в деревьях kd данные разбиваются на две области на основе некоторого анализа данных (например, медиана некоторой координаты). Деревья квадрантов плохо масштабируются до больших размеров из-за экспоненциальной зависимости размерности. Структуры данных также различаются по сложности времени запроса.
Поскольку вас интересуют 2D-точки, вам может подойти любая структура данных. Деревья KD очень легко запрашивать диапазоны, и обычно они предпочтительнее деревьев квадрантов. Я предлагаю вам использовать их.
person
killogre
schedule
26.11.2012
Осторожно: kd-деревья также экспоненциально масштабируются по количеству измерений. Основное отличие заключается в том, что kd-деревья оказываются глубже, но уже.
- person Apollys supports Monica; 27.12.2018
Как глубина связана с количеством измерений? Разве глубина не $\log(N)$?
- person Eduardo Reis; 27.05.2020
@EduardoReis В d-мерной версии quadtree ширина экспоненциальна по глубине. Журнал глубины (N) только в том случае, если данные сбалансированы, что маловероятно.
- person killogre; 03.06.2020
