| The convex hull of a finite set of a set S of n planar points is an important geometric concept. It can be defined as the smallest convex polygon for which each point in S is either on the boundary of the convex polygon or in its interior. The convex hull problem has many applications in areas such as statistics, pattern recognition, computer graphics, economics, and computer-aided design.; In this document, several new parallel algorithms for the convex hull problem are presented. Parallel algorithms for the Jarvis March, QuickHull, Graham Scan and QuickGraham are developed. These algorithms do not require sorting of the input points and do not require a communication network. In addition, these algorithms are iterative and easier to implement on parallel than the divide and conquer algorithms on parallel computers. A communication network can be used which makes our algorithms optimal for that architecture.; The computational model selected for these algorithms is the Multiple Associative Model (MASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, MASC can be supported on existing SIMD computers. |
