Efficient parallel sibling finding for quadtree data structure
D.P. Doctor, Hal Sudborough · 2002
This paper presents efficient parallel (hypercube and EREW-PRAM) algorithms for building pointer-based and linear quadtrees from boundary/chain code image representation. For the input boundary code of length O(b) and the height O(h) of the output quadtree, over EREW-PRAM algorithm takes O(h + logb) time and O(b) processors for quadtree building from boundary code; this improves upon a previously published CREW-PRAM algorithm requiring O(h * logb) time and O(b) processors; which also improves upon a previously published hypercube algorithm requiring O(logb(h + log/sup 2/logb)) time and O(b) processors. The algorithms, presented here, use a direct and simple sibling finding technique for quadtrees; our technique exploits regularity in quadtree data structure, and it is applicable to any k-ary tree for which some (arbitrary) ordering exists among child nodes of a parent node.>