COMPUTATIONAL GEOMETRY ON A MESH-CONNECTED COMPUTER.

It is shown that the mesh-connected computer can be used for more than low-level, local image processing. The authors present optimal algorithms, in the O-notational sense, for determining several fundamental geometric properties. For example, given a figure represented by the Cartesian coordinates of O(n) planar points, distributed one point per processor on a mesh-connected computer, theta (n**1 **/ **2 ) algorithms are given for identifying the convex hull of the figure and for determining a smallest enclosing box of the figure. Given two such figures, theta (n**1 **/ **2 ) algorithms are given to decide if the two figures are linearly separable. Also given is a theta (n**1 **/ **2 ) algorithm for determining the nearest neighbor of each of the O(n) planar points. Since any serial computer has a best-case time of theta (n) when processing O(n) points, these algorithms show that the mesh-connected computer provides significantly better solutions to these problems.