В большинстве (всех?) Реализаций быстрого мультипольного метода (FMM) октоды используются для декомпозиции соответствующей области. Теоретически, октреи предоставляют простую объемную границу, которая полезна для доказательства O (n) времени выполнения FMM. Помимо этого теоретического обоснования, есть ли преимущества использования Octree по сравнению с другими структурами дерева или дерева данных?
Определение списка взаимодействия может быть проще с октодеревом, потому что ячейка будет знать своих непосредственных соседей. Однако в списке взаимодействий нет необходимости, используя более динамический обход дерева, такой как Dual Tree Traversal .
Альтернативой будет kd-дерево. Одним из возможных теоретических недостатков является то, что для строительства требуются дорогостоящие операции по поиску медианы. Однако существуют версии kd-деревьев, которые не требуют медианного поиска во время построения, хотя и с менее эффективным разделением пространства. С точки зрения реализации, kd-дерево очень просто.
Еще более радикальной альтернативой может быть R-дерево .
Итак, мой вопрос: как насчет Octrees, которые делают их лучшим выбором для FMM?
источник
Ответы:
Приведенные выше комментарии дают несколько очень веских причин для использования октодеревьев (т. Е. Рекурсивного деления вычислительного куба пополам в каждом измерении в отличие от более общего ортогонального деления пополам). Симметрия и простота расчета списков взаимодействий - большой плюс.
Я бы сказал, что, пожалуй, самая важная особенность, которую октры привносят в таблицу, заключается в том, что теорема сложения, лежащая в основе FMM, систематически выполняется для взаимодействий в дальней зоне, не зависящих от геометрии, с чрезвычайно простым критерием четкого разделения одного или нескольких «буферов». коробки. Другими словами, представление FMM-суммы потенциального поля гарантированно сходится с возрастающим порядком при непатологических обстоятельствах.
источник