Octree

Octree
TypeTree
Invented1980
Invented byDonald Meagher
Time complexity in big O notation
Operation Average Worst case
Search O(logN+K) O(logN+K)
Insert O(logN) O(logN)
Delete O(logN) O(logN)
Peek O(logN) O(logN)
Space complexity
Space O(N) O(N)

An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The word is derived from oct (Greek root meaning "eight") + tree. Octrees are often used in 3D graphics and 3D game engines.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.