octree
Sign in to savethumb|Left: Recursive subdivision of a cube into octant (solid geometry)|octants. Right: The corresponding octree.
Key facts
- Data structure.name
- Octree
- Data structure.type
- Tree
- Data structure.invented_by
- Donald Meagher
- Data structure.invented_year
- 1980
- Data structure.space_avg
- O(N)
- Data structure.space_worst
- O(N)
- Data structure.search_avg
- O(logN+K)
- Data structure.search_worst
- O(logN+K)
- Data structure.insert_avg
- O(logN)
- Data structure.insert_worst
- O(logN)
- Data structure.delete_avg
- O(logN)
- Data structure.delete_worst
- O(logN)
- Data structure.peek_avg
- O(logN)
- Data structure.peek_worst
- O(logN)
via Wikipedia infobox
Article
9 sectionsContents
- For spatial representation
- History
- Common uses
- Application to color quantization
- Implementation for point decomposition
- Example color quantization
- See also
- References
- External links
thumb|Left: Recursive subdivision of a cube into octant (solid geometry)|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.