Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.1, pp.81-102 (March 1993)
Efficient Parallel Neighbor Finding Algorithms
for Quadtrees on Hypercubes*

Shi-Nine Yang and Ruen-Rone Lee
Department of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 300, R.O.C.

In this paper we introduce efficient parallel quadtree neighbor finding algorithms on hypercube multiprocessors. We observe that most existing parallel quadtree neighbor finding algorithms regard quadtree nodes only as combinatorial objects. Therefore, the restoration of geometric relations requires extra data movements and communication overhead by either sorting the quadtree nodes or traversing the embedded quadtree. Our approach considers the quadtree nodes as both combinatorial objects and geometric entities with spatial adjacency relations. By requiring the preserving of adjacency relations during the quadtree construction phase, we propose new parallel neighbor finding algorithms for finding edgeneighbors and corner-neighbors of all leaf nodes in a quadtree. Theoretical analysis and empirical testing are given to show that our algorithms are efficient and better than existing algorithms both in time and communication aspects.

Keywords: hypercube, quadtree, neighbor-finding, parallel algorithm, computer graphics

Received November 21, 1992; revised February 1, 1993.
Communicated by Shing-Tsaan Huang.
*This work is supported by the national Science Council, Taiwan, Republic of China, under grant NSC81-0416-E-007-01.
The preliminary result has been presented at the ICPADS'92, 1992 International Conference on Parallel and Distributed Systems, December 16-18, 1992, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.