TY - JOUR

T1 - Finding all nearest neighbors for convex polygons in parallel

T2 - A new lower bound technique and a matching algorithm

AU - Schieber, Baruch

AU - Vishkin, Uzi

N1 - Funding Information:
* The research of this author was supported by NSF grant NSF-CCR-8615337, ONR grant N00014-85-K-0046, the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract number DE-AC02-76ER03077 at the Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities at Tel Aviv University.

PY - 1990/11

Y1 - 1990/11

N2 - 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≤ji 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.

AB - 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≤ji 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.

UR - http://www.scopus.com/inward/record.url?scp=38249018367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249018367&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(90)90084-P

DO - 10.1016/0166-218X(90)90084-P

M3 - Article

AN - SCOPUS:38249018367

VL - 29

SP - 97

EP - 111

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1

ER -