PLANAR CONVEX HULL ALGORITHMS ON LINEAR ARRAYS
Doris L. Carver, Jigang Liu, Si Zheng · International Journal of Parallel Emergent and Distributed Systems · 1996
This paper presents two planar convex hull algorithms on linear array. The First algorithm is for the case such that n ≤ p, where n and p are the number of points in S and the number of processors, respectively. The algorithm runs in O(n) which is optimal. The second algorithm is designed for a general case such that n > p. The algorithm runs in O((n/p) log(n/p)) time, which is also optimal. Both algorithms have been extended to d-dimensional mesh-connected array with O(d2n1/d ) in time for the case such as n > p and p 1/ >> 2, which are both optimal.