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 Θ(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 Θ(n²).

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

Reference: This paper appears in IEEE Transactions on Pattern Analysis and Machine Intelligence 7 (1985), pp. 216-228.

• Most of the contents of this paper have been incorporated into the book   Parallel Algorithms for Regular Architectures: Meshes and Pyramids
• My papers in parallel computing
• Overview of my research in parallel computing

Copyright © 2005-2008 Quentin F. Stout