Quadtree Building Algorithms on an SIMD Hypercube

✍ Scribed by O.H. Ibarra; M.H. Kim

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 555 KB
• Volume: 18
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1993.1045

✦ Synopsis

We present (O(\log n)) time SIMD hypercube algorithms for transforming binary images to linear quadtrees and vice versa, where (n) is the size of the images as well as the number of hypercube nodes. Our quadtree building algorithm, which generates the locational codes in preorder, is an improvement of a recently reported algorithm that runs in (O\left(\log ^{2} n\right)) time. We also give an optimal linear quadtree building algorithm which runs in (T(n)) time using (n^{2} / T(n)) processors for (\log n \leq T(n) \leq n^{2}). The algorithm is optimal in the sense that the product of time and number of processors is asymptotically the same as the optimal sequential time which is (O\left(n^{2}\right)). For this algorithm we assume that the input binary image is divided into blocks and loaded in a shuffled row major ordered hypercube. The algorithm uses the procedures for the quadtree building algorithm developed for the case when the number of hypercube nodes is equal to the number of pixels in the binary image. 1993 Academic Press. Inc.