A 2-D parallel convex hull algorithm with optimal communication phases

We investigate the problem of finding the 2-D convex hull of a set of point s on a coarse-grained parallel computer, Goodrich has devised a parallel so rting algorithm for n items on P processors which achieves an optimal numbe r of communication phases for all ranges of P less than or equal to n. Ferr eira et al. have recently introduced a deterministic convex hull algorithm with a constant number of communication phases for n and P satisfying n gre ater than or equal to P1+is an element of. Here we present a new parallel 2 -D convex hull algorithm with an optimal bound on number of communication p hases for all values of P less than or equal to n while maintaining optimal local computation time. (C) 2001 Elsevier Science B.V, All rights reserved .