Hypercube algorithms for parallel processing of pointer based quadtrees.

F. Dehne, A. Ferreira, and A. Rau-Chaplin

Abstract: This paper studies the parallel construction and manipulation of pointer based quadtrees on the hypercube multiprocessor. While parallel algorithms for the manipulation of a variant of linear quadtrees have been previously studied in the literature, no parallel pointer based quadtree construction algorithms have been presented. In this paper, we solve the problem of efficiently constructing pointer based quadtrees on the hypercube, from images represented by either binary matrices or boundary codes. In addition we show how these algorithms can be efficiently implemented on the PRAM providing new construction algorithms for both pointer based and linear quadtrees. Furthermore, previous papers considered exclusively the parallel processing of a variant of linear quadtrees, namely linear quadtrees with path encoding. In this paper, we demonstrate that, in the parallel setting, pointer based quadtrees are an attractive alternative to linear quadtrees with path encodings. We present new efficient and practical parallel algorithms for standard quadtree operations, (such as finding the neighbors of all leaves in a quadtree, and computing the union/intersection of two quadtrees) for the hypercube.