Tree structures that divide space so that points, shapes and regions can be found quickly without comparing every item. The k-d tree splits points along alternating axes, the quadtree and octree split a plane or a volume into four or eight parts, and the R-tree groups nearby objects inside bounding rectangles. They are used in map software, games, graphics and databases whenever a program must ask what lies near a given place.
Spatial Index Structures
Filter Results4 entries
Sources
NIST Dictionary of Algorithms and Data Structures: k-d tree
NIST Dictionary of Algorithms and Data StructuresHas Member: K-d Tree Algorithm, DefinitionQuote, Has Member: K-d Tree Algorithm, Definition
A multidimensional search tree for points in k dimensional space.
NIST Dictionary of Algorithms and Data Structures: R-tree
NIST Dictionary of Algorithms and Data StructuresHas Member: R-Tree Algorithm, DefinitionQuote, Has Member: R-Tree Algorithm, Definition
A spatial access method that splits space with hierarchically nested, and possibly overlapping, boxes.
NIST Dictionary of Algorithms and Data Structures: quadtree
NIST Dictionary of Algorithms and Data StructuresHas Member: Quadtree Algorithm, DefinitionQuote, Has Member: Quadtree Algorithm, Definition
A tree where each node is split along all d dimensions, leading to 2 d children.
NIST Dictionary of Algorithms and Data Structures: octree
NIST Dictionary of Algorithms and Data StructuresHas Member: Octree Algorithm, DefinitionQuote, Has Member: Octree Algorithm, Definition
A tree to index three dimensions.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.