A new parallel quadtree construction algorithm on a hypercube

Most existing parallel quadtree construction algorithms regard quadtree nodes only as combinatorial objects. Therefore, the restoration of geometric relations requires extra communication overhead by either traversing the embedded quadtree or sorting the quadtree nodes. A different approach is adopted. It considers the quadtree nodes as both combinatorial objects as well as geometric entities with spatial adjacency relations. By incorporating the notion of adjacency preserving, a new parallel quadtree construction algorithm is proposed. It is shown to be efficient in both time and communication aspects. The initial data loading process is investigated, and an efficient loading algorithm is proposed to provide a better structure for the following construction phase