Parallel Quadtree Construction and Manipulation Algorithms on Hypercube

[[abstract]]In this paper we introduce efficient parallel quadtree construction and manipulation algorithms on hypercube multiprocessors. The notion of extended binomial tree is introduced to represent the distributed quadtree structure on a hypercube. By incorporating the geometric property into the distributed quadtree structure, we devise a data assignment scheme which satisfies the multi-level adjacency preserving (MAP) property. We show that the distributed data structure together with geometric constraint not only results in an efficient parallel quadtree construction, but also facilitates several graphics and image processing operations, such as neighbor finding, perimeter computation and border extraction, on constructed quadtree. Theoretical analysis and empirical testing are given to show that the proposed algorithms are better than existing algorithms both in time and communication aspects.[[fileno]]2030205030020[[department]]資訊工程學