PARALLEL ALGORITHMS FOR SOME FUNCTIONS OF TWO CONVEX POLYGONS t

Abstract. Let P and Q be two convex, n-vertex polygons. We consider the problem of comput-mg, in parallel, some functions of P and Q when P and Q are disjoint The model of parallel computation we consider is the CREW-PRAM, Le. it is the synchronous shared-memory model where concwrem reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PR.A.L\1 having n llk processors can compute the following fimctions in o(k 1+£) time: (i) The common tangents between P and Q. (ii) The distance be[Ween P and Q (and hence a straight line separating them). The positive constant E can be made arbilIarily close to zero. Even with a linear number of processors. it was not previously known how to achieve constam time perfor-mance for computing these functions