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 (miller@cse.buffalo.edu)