Title :
A BSP realisation of Jarvis´s algorithm
Author :
Cinque, L. ; Di Maggio, C.
Author_Institution :
Dipt. di Matematica Pura ed Applicata, Rome Univ., Italy
Abstract :
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
Keywords :
computational complexity; computational geometry; parallel algorithms; BSP realisation; IBM SP2; Jarvis march; algorithm testing; bulk synchronous parallel model; complexity; convex hull; cost calculus model; parallel algorithm; performance prediction; Algorithm design and analysis; Application software; Computational geometry; Concurrent computing; Costs; Parallel algorithms; Phase change random access memory; Remuneration; Standards development; Testing;
Conference_Titel :
Image Analysis and Processing, 1999. Proceedings. International Conference on
Conference_Location :
Venice
Print_ISBN :
0-7695-0040-4
DOI :
10.1109/ICIAP.1999.797603
