Detection of connectivity for regions represented by linear quadtrees

AbstractAn algorithm is given for the determination of all connected components of a given region. The data structure used to represent the region (or image) is the linear quadtree, a recently introduced structure which basically consists of a sorted array of quaternary integers. A linear quadtree is built in a way similar to that of a regular quadtree but contains, as elements, only black nodes. The proposed algorithm has computational complexity proportional to 12nN, where n is the resolution parameter of the image, and N is the number of black nodes. Space complexity is proportional to 6N. The algorithm is shown to compare favourably, both in terms of space and time, with the existing method due to H. Samet