Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays

Linear arrays are characterized by a small communication bandwidth and a large communication diameter rendering them unsuited to the implementation of global computations. This paper presents efficient data movement and partitioning techniques to overcome several shortcomings of linear arrays. These techniques are used to derive optimal parallel algorithms for several geometric problems on n×n images using a fixed-size linear array with p processors, where 1≤p≤n. O(n²/p) time solutions are presented for labeling connected image regions, computing the convex hull of each region, and computing nearest neighbors. Consequently, a linear array with n processors can solve several image problems in O(n) time which is the same time taken by a two dimensional mesh-connected computer with n² processors. Limitations of linear arrays are analyzed by presenting a class of image problems which can be solved sequentially in O(n)²) time, but require Ω(n²) time on a linear array, irrespective of the number of processors used and the partitioning of the input image among the processors. An alternate communication-efficient fixed-size organization with p processors is proposed to solve such problems in O(n²/p) time, for 1≤p≤n.