Tree data structures for N-body simulation
Tree data structures for N-body simulation
复制标题
DOI：
10.1109/sfcs.1996.548481
复制
发表时间：
1996-10
期刊：
影响因子：
--
通讯作者：
Richard J. Anderson
中科院分区：
文献类型：
--
作者：
Richard J. Anderson
在本文中，我们研究用于N体模拟的数据结构。我们专注于粒子 - 聚类力评估算法（如Barnes - Hut算法）中使用的空间分解树。我们证明k - d树在渐近意义上劣于空间平衡树。我们表明使用k - d树的力评估算法的最坏情况复杂度为Θ(nlog³nlogL)，而八叉树为Θ(nlogL)。（L是点集的分离比。）我们还研究了改进算法的常数因子，并提出了几种优于标准八叉树分解的方法。最后，我们考虑点集的包围盒是否应该是“紧密的”，并表明只有对于二叉分解使用紧密包围盒才是安全的。这些结果都直接适用于N体算法的实际实现。
In this paper, we study data structures for use in N-body simulation. We concentrate on the spatial decomposition tree used in particle-cluster force evaluation algorithms such as the Barnes-Hut algorithm. We prove that a k-d tree is asymptotically inferior to a spatially balanced tree. We show that the worst case complexity of the force evaluation algorithm using a k-d tree is /spl Theta/(nlog/sup 3/nlogL) compared with /spl Theta/(nlogL) for an oct-tree. (L is the separation ratio of the set of points.) We also investigate improving the constant factor of the algorithm, and present several methods which improve over the standard oct-tree decomposition. Finally, we consider whether or not the bounding box of a point set should be "tight", and show that it is only safe to use tight bounding boxes for binary decompositions. The results are all directly applicable to practical implementations of N-body algorithms.