Quadtrees and Hypercubes: Grid Embedding Strategies Based on Spatial Data Structure Addressing
Leila Anne Breene · The Computer Journal · 1993
A uniform toroidal addressing scheme for k-trees, or spacial data structures, is given. These include bintrees, for decomposing the line, or partitioning linear arrays; quadtrees, for two-dimensional structures; octrees, for three dimensions; etc. Reinterpretation of these addresses as hypercube node identifiers affords simple conceptualization of processor grids of arbitrary Euclidean dimension. Use of gray code produces a hierarchy of topological neighborhoods reflected in the addresses themselves and, with this, fast multicast algorithms for various multiple-processor subgroups.