Quadtree building algorithms on an SIMD hypercube
Óscar H. Ibarra, M.H. Kim · 2003
Presents O(log n) time SIMD hypercube algorithms for transforming binary images to linear quadtrees and vice versa, where n is the size of the images as well as the number of hypercube nodes. The quadtree building algorithm, which generates the locational codes in preorder, is an improvement of a recently reported algorithm that runs in O(log/sup 2/n) time. The authors also give an optimal linear quadtree building algorithm which runs in T(n) time using n/sup 2//T(n) processors for log n>