Linear quadtree algorithms for transputer array

Abstract

The quadtree is a hierarchical data model based upon a regular recursive decomposition of space, which has been found useful in such areas as image processing, computer graphics, cartography and spatial information systems. The linear quadtree is a pointerless representation of the quadtree. In the paper, a number of linear quadtree algorithms are presented for a transputer array. These form a largely complementary set to those developed by Bhaskar et al. [1] for a similar multiprocessor architecture. Emphasis is placed on algorithms which require the neighbours of quadtree leaves to be accessed. These include perimeter computation, connected component labelling and image dilation. A quadtree generation algorithm is also described. Timing estimates have been carried out using a transputer development system. A price to be paid for the speed increases achieved is an increase in the complexity of the multiprocessor algorithms.