octree

(data structure)

Definition: A tree to index three dimensions. Each node has either eight children or no children.

See also quadtree, binary tree, BSP-tree.

Note: If one views a binary tree as partitioning one dimension, a quadtree analogously partitions two dimensions, and an octree partitions three.

Author: PEB

More information

algorithms, another diagram and algorithm, and one more diagram from Martin John Baker. Another diagram from Nilo Stolte.

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

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

Entry modified Tue Jan 3 10:39:09 2006.
HTML page formatted Tue Jan 3 10:39:20 2006.

Cite this as:
Paul E. Black, "octree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/octree.html