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 optimal algorithms for computing several geometric properties of figures. Given a black/white picture, a component is a connected region of black pixels. If the image is 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,
• deciding if the convex hull of each component contains pixels that are not members of the component,
• deciding if two components are linearly separable,
• deciding if each component is convex,
• determining the distance to the nearest neighboring component of each component,
• determining internal distances in each component,
• counting and marking minimal internal paths in each component,
• computing the external diameter of each component,
• solving the largest empty circle problem,
• determining internal diameters of components without holes, and
• solving the all-points farthest point problem.

Keywords: mesh computer, array processor, computational geometry, convexity, digitized images, digital geometry, minimal paths, nearest neighbors, diameter, farthest points, divide-and-conquer, parallel computing, parallel algorithms, computer science

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

• Most of the contents of this paper are incorporated into our book R Miller and QF Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996
• My papers in parallel computing
• Overview of my research in parallel computing
• A somewhat whimsical explanation of parallel computing

Copyright © 2005-2018 Quentin F. Stout