Browse by author
Lookup NU author(s):
Full text is not currently available for this publication.
The convex hull is a problem of primary importance because of its applications in computational geometry. A number of sequential and parallel algorithms for computing the convex hull os a finite set of points in the lower dimensions are known. In comparison, the general n-D problem is not as well understood and parallel algorithms are not so prevalent because the 2-D and 3-D methods are not easily extended to the general case. This thesis presents parallel algorithms for evaluating the general n-D convex hull problem (where 2-D and 3-D are special cases) using Swart's sequential algorithm. One of our methods combines a gift-wrapping technique with partitioning and merge algorithms where the original list is split into p > 1 partitions followed by the computation of the subhulls using the sequential n-D gift wrapping method. The partial hulls are then combined using a fannin tree. The second method computes the convex hull in parallel by wrapping around the edges until a complete facial lattice structure of the polytope is generated. Several parameterised versions of the proposed algorithms have been implemented on the shared memory and message passing architectures. In the former, performance on an Encore Multimax using Encore Parallel Threads and the more lightweight Mecrothread programming utilities are examined. In the latter, performance on a transputer based machine using CS-Tools is discussed. We have shown that our techniques will be useful in the construction of faster algorithms which exploy the n-D convex hull algorithms as a sub-algorithm.
Author(s): Eyoh EO
Publication type: Report
Publication status: Published
Series Title:
Year: 1994
Institution: Department of Computing Science, University of Newcastle upon Tyne
Place Published: Newcastle upon Tyne
