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 points on a coarse-grained parallel computer, Goodrich has devised a parallel sorting algorithm for n items on P processors which achieves an optimal number of communication phases for all ranges of P less than or equal to n. Ferreira et al. have recently introduced a deterministic convex hull algorithm with a constant number of communication phases for n and P satisfying n greater 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 phases 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.
convex hull communication parallel algorithms