FINDING THE CONVEX-HULL OF DISCS IN PARALLEL

We present a parallel method for finding the convex hull of planar dis cs in the EREW PRAM model. We show that the convex hull of n discs in the plane can be computed in O(log(1+epsilon) n) time using O(n/log(ep silon) n) processors or in O(log n log log n) time using O(n log(1+eps ilon) n) processors for any positive constant epsilon. The first resul t achieves cost optimal and the second one runs faster. We also show t hat the convex hull of planar discs can be constructed in O(log n) tim e using O(n) processors when the number of different kinds of radii is restricted to 2(O(log alpha n)) for any positive constant alpha with 0 < alpha < 1. Finally, we show that our method can be generalized to computing the convex hull of a large class of planar curves. We use a technique called multi-level divide-and-conquer in our algorithm.