Parallel Algorithms for Constructing Convex Hulls.

For a given set of planar points S, the convex hull of S, CH(S), is defined to be a list of ordered points which represents the smallest convex polygon that contains all of the points. The convex hull problem, one of the most important problems in computational geometry, has many applications in areas such as computer graphics, simulation and pattern recognition. There are two strategies used in designing parallel convex hull algorithms. One strategy is the divide-and-conquer paradigm. The disadvantage to this strategy is that the recursive merge step is complicated and difficult to implement on current parallel machines. The second strategy is to parallelize sequential convex hull algorithms. The algorithms designed using the second strategy are often iterative algorithms which can be more easily implemented on the current parallel machines. This research focuses on designing parallel convex hull algorithms using the second strategy because we intend to facilitate the implementation of the newly designed algorithms on massively parallel machines. We first design a sequential algorithm for constructing a convex hull of a simple polygon, which is a special case of a set of planar points. This optimal algorithm is extended to handle a set of planar points without increasing the time complexity. Next, the sequential algorithm is converted for linear array and two or more dimensional mesh-array architectures. The algorithms for the case where the number of points is greater than the number of processors is also addressed. Each of the algorithms developed is optimal. To analyze the performance of the algorithms compared to previous algorithms, a system called the Parallel Convex Hull Simulation System was developed. The results of the analysis indicate that the new algorithms exhibit better performance than previous algorithms