In IEEE Transactions on Pattern Analysis and Machine Intelligence 7 (1985), pp. 216-228.

Geometric Algorithms for Digitized Pictures on a Mesh-Connected Computer

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

Quentin F. Stout
EECS Department, University of Michigan

Abstract: Although mesh-connected computers are used almost exclusively for low-level local image processing, they are also suitable for higher level image processing tasks. We illustrate this by presenting new optimal algorithms for computing several geometric properties of figures. For example, given a black/white picture stored one pixel per processing element in an n x n mesh-connected computer, we give Theta(n) time algorithms for determining the extreme points of the convex hull of each component, for deciding if the convex hull of each component contains pixels that are not members of the component, for deciding if two sets of processors are linearly separable, for deciding if each component is convex, for determining the distance to the nearest neighboring component of each component, for determining internal distances in each component, for counting and marking minimal internal paths in each component, for computing the external diameter of each component, for solving the largest empty circle problem, for determining internal diameters of components without holes, and for solving the all-points farthest point problem. Previous mesh-connected computer algorithms for these problems were either nonexistent or had worst case times of Theta(n2).

Keywords: mesh computer, computational geometry, convexity, digitized images, digital geometry, minimal paths, nearest neighbors, diameter, farthest points, divide-and-conquer, parallel computing, parallel algorithms, 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 (