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
SN - 0166-218X
VL - 29
SP - 97
EP - 111
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1
ER -