(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 Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "BD-tree", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bdtree.html