**Abstract:**
We present asymptotically optimal
parallel algorithms for using a mesh computer to determine
several fundamental geometric
properties of figures.
For example, given multiple figures represented by the Cartesian coordinates
of *n* or fewer planar vertices,
distributed one point per processor on a 2-dimensional mesh computer with
*n* simple processing elements, we give *Theta(sqrt(n))* algorithms
for identifying the convex hull and smallest enclosing box of each figure.
Given two such figures, we give a *Theta(sqrt(n))* algorithm to
decide if the two figures are linearly separable.
Given *n* or fewer planar points, we give *Theta(sqrt(n))* time
algorithms to solve the all-nearest neighbor problem for points
and for sets of points.
Given *n* or fewer
circles, convex figures, hyperplanes, simple polygons, orthogonal polygons, or
iso-oriented rectangles, we give
*Theta(sqrt(n))* time algorithms to solve a variety of area and
intersection problems.
Since any serial computer has worst-case time of
*Omega(n)* when processing *n* points, our algorithms
show that the mesh computer provides significantly
better solutions to these problems.
**Keywords:** parallel algorithm, mesh computer, computational geometry,
planar point data, convexity, proximity, area, intersection, parallel
computer, discrete mathematics, computer science.