About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
Abstract
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.