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

We investigate the problem of finding the two-dimensional convex hull of a set of points on a coarse-grained parallel computer. Recently 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⩽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⩾P^1+ε. Here we obtain a new parallel 2-D convex hull algorithm with an optimal bound on number of communication phases for all values of P⩽n while maintaining optimal local computation time