F. Dehne et al., HYPERCUBE ALGORITHMS FOR PARALLEL-PROCESSING OF POINTER-BASED QUADTREES, Computer vision and image understanding, 62(1), 1995, pp. 1-10
Citations number
18
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Software Graphycs Programming
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.