A parallel method for finding the convex hull of discs

We present a parallel method for finding the convex hull of a set of discs in the CREW PRAM model. We show that the convex hull of n discs can be computed in O(log^1+ε n) time using O(n/log^ε n) processors, where ε is any positive constant. We also show that it can be constructed in O(log n loglog n) time using O(n log n) processors. The first result achieves cost optimal and the second one runs faster. The main technique which we used in the algorithm is a complex divide-and-conquer technique