An Associative Implementation of Graham's Convex Hull Algorithm.
Maher M. Atwah, Johnnie W. Baker, Selim G. Akl · 1995
This paper presents a new parallel algorithm for the convex hull problem. This algorithm is a parallel adaptation of the Graham Scan Algorithm. The computational model selected for this algorithm is the associative computing model (ASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on existing SIMD computers. This algorithm requires O(n) space, O(n log n) average cost, and O(n²) worst case cost. The algorithm has been implemented and tested on random data.