Parallel algorithms for some functions of two convex polygons (Q1105374)

Let P and Q be two convex, n-vertex polygons. We consider the problem of computing, 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, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but not 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-PRAM having \(n^{1/k}\) processors can compute the following functions in \(O(k^{1+\epsilon})\) time: (i) the common tangents between P and Q, and (ii) the distance between P and Q (and hence a straight line separating them). The positive constant \(\epsilon\) can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.