Russ Miller

Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout

Computer Science and Engineering, University of Michigan

**Abstract**:
We present parallel algorithms to enumerate
the extreme points of a set of planar points.
The parallel
computers considered are the hypercube, pyramid, tree, mesh-of-trees,
mesh with reconfigurable bus (rmesh), EREW PRAM, and a modified
AKS sorting network. It is known that the problem of identifying the convex
hull for a set of planar points given arbitrarily cannot be solved
faster than sorting real numbers. When the input set of
*n* points is given in sorted order (by x-coordinate) one per processor
on a machine with Θ(n) processors, our algorithms for

- a hypercube takes Θ(log n) time,
- a pyramid, binary tree, or mesh-of-trees take
Θ((log
^{3}n)/(log log n)^{2}) time, - a reconfigurable mesh takes Θ(log
^{2}n) time, and - a CREW PRAM takes Θ(log n) time.

The time for the CREW PRAM is achievable if the input is unsorted since the input can be sorted in O(log n) time. Thus for unsorted input it is optimal.
Previous PRAM algorithms were either slower or required concurrent read or write
operations. We also show that this algorithm
can be extended to run in Θ(log n) time on a modified AKS
sorting network, giving the first optimal Θ(log n) algorithm for
solving the convex hull problem for arbitrary planar input on a fixed
degree network with *n* processors.
However, this is only of theoretical interest since the constants on the AKS network make it highly impractical.

In another paper we show that the convex hull can be determined in
Θ(n^{1/2}) time on a 2-dimensional
mesh-connected computer.
This too is optimal, and that paper includes optimal algorithms for many
other problems as well.
Many of these easily extend to optimal algorithms on d-dimensional meshes, taking Θ(n^{1/d}) time, where the implied constants depend upon d.
Optimal algorithms for the pyramid, tree, mesh-of-trees, and
reconfigurable mesh are open problems.

If the points are chosen uniformly and independently from the unit square then the convex hull can be found in Θ(1) expected time using a CRCW PRAM with a weak concurrent write (either common write or collision detection). This is true even if the points are not sorted in advance. For such input fast expected case algorithms can also be developed for the pyramid, binary tree, mesh-of-trees, and reconfigurable mesh.

**Keywords**: parallel computer, convex hull,
AKS sorting network, computational geometry, EREW PRAM,
hypercube, mesh connected computer, mesh-of-trees, reconfigurable mesh,
pyramid computer, parallel
algorithm

**Complete paper**.
It appears in *IEEE Trans. Computers* **C-37** (1988),
pp. 1605-1618.

**Related work:**

A modest
explanation of parallel computing, a
tutorial, Parallel Computing 101, and a
list of parallel computing resources.

An
overview of our work, and
relevant papers.

Copyright © 2008-2018 Quentin F. Stout. |