(data structure)
Definition: A binary tree that organizes multidimensional points by splitting off regular subintervals.
Generalization (I am a kind of ...)
binary tree, point access method.
Note: After [GG98].
Author: PEB
Yutaka Ohsawa and Masao Sakauchi, BD-Tree: A New N-dimensional Data Structure with Efficient Dynamic Characteristics, Proc. 9th World Computer Congress, IFIP83, pp. 539-544, 1983.
"Bounded deformation" trees for collision resolution are described in
Doug L. James and Dinesh K. Pai, BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models, ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 August 2008.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "BD-tree", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 August 2008. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/bdtree.html