Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm

The main contribution of this paper is a novel technique for proving lower bounds in parallel computation. The technique is based on mapping any algorithm for the problem being considered to an algorithm for another problem, for which a good lower bound is known. The mapping is done by careful application of Ramsey-like arguments. Specifically, we study the parallel complexity of the following problem. Given an input convex polygon P=(υ0,...,υn-1), where (υi, υi+1) (the indices are taken modulo n) is an edge of P, for i=0,...,n-1, find the nearest neighbor of each vertex υi of P. That is, find a vertex υj,j≠i, 0≤j<n, whose (Euclidean) distance from υi is minimal. We present a parallel algorithm for the problem which runs in O(log log n) time using n/log log n processors on a CRCW PRAM. We prove that Ω(log log n) time is needed for solving the problem on a CRCW PRAM with O(n logcn) processors, for any constant c. © 1990.