NIST

BD-tree

(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

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2008.
HTML page formatted Fri Feb 23 10:06:07 2018.

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: https://www.nist.gov/dads/HTML/bdtree.html