Russ Miller

Dept. of Computer Science, 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 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-2017 Quentin F. Stout |