In Algorithmica 6 (1991), pp. 658-684.

Computing Convexity Properties of Images on a Pyramid Computer

Russ Miller
Dept of Comp Sci & Eng, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: We present efficient parallel algorithms for using a pyramid computer (a parallel computer connected in a specific, pyramidal pattern) to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base of n simple processing elements arranged in an n1/2 x n1/2 square, the running times of the algorithms range from Theta(log n) to find the extreme points of a convex figure in a digitized picture, to Theta(n1/6) to find the diameter of a labeled figure, to Theta(n1/4 log n) to find the extreme points of every figure in a digitized picture, to Theta (n1/2) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.

Keywords: Pyramid computer, convexity, digitized pictures, digital geometry, image processing, parallel computing, parallel algorithms, data movement operations, bandwidth limitations, lower bounds, computer science

Much of the content of this paper has been incorporated into the book Parallel Algorithms for Regular Architectures: Meshes and Pyramids, by R. Miller and Q.F. Stout. More information about the book is available.

Russ Miller (