Tree data structure in which each internal node has exactly eight children, to partition a 3D space
| Octree |
|---|
| Type | Tree |
|---|
| Invented | 1980 |
|---|
| Invented by | Donald Meagher |
|---|
|
| 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 |
O(N) |
O(N) |
|---|
|
Left: Recursive subdivision of a cube into octants. Right: The corresponding octree.
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.
