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=(υ₀,...,υ_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 log^cn) processors, for any constant c.