A BSP realisation of Jarvis's algorithm
Luigi Cinque, C. Di Maggio · 2003
The purpose of this paper is to present a very efficient parallel algorithm for computing the convex hull in the plane. We propose a parallel version of the Jarvis's march, realized using the BSP model and which takes O(nh/p) time (where p is the number of processors and n is the problem size) against the O(nh) complexity of the sequential algorithm. Furthermore, we give the experimental results obtained testing the algorithm implementation on a 16-node IBM SP2 (Scalable POWER parallel 2) and we compare them with the theoretical performance prediction obtained using the BSP cost calculus model.