HYPERCUBE ALGORITHMS FOR PARALLEL-PROCESSING OF POINTER-BASED QUADTREES

This paper studies the parallel construction and manipulation of point er-based quadtrees on fine grained hypercube multiprocessors. Previous papers considered the parallel processing of linear quadtrees. Here w e show that parallel pointer-based quadtrees are a viable alternative. We first solve the problem of efficiently constructing a pointer-base d (or linear) quadtree from an image represented either by a binary ma trix or a boundary code. Then we present efficient parallel manipulati on algorithms for pointer-based quadtrees, such as finding the neighbo rs of all leaves in a quadtree or computing the union/intersection of two quadtrees. These algorithms improve on existing time complexities and can be implemented in fine grained hypercube systems (e.g., the Co nnection Machine CM2). In the expected case, the space complexity is t he same as for previous methods. In the worst case (of a degenerated q uadtree), the space complexity increases by a factor which, for the hy percube, is smaller than the time complexity improvement. As a byprodu ct of our hypercube algorithms, we also obtain some PRAM algorithms fo r quadtrees that improve on known results. (C) 1995 Academic Press, In c.