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

Baruch Schieber, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)97-111
Number of pages15
JournalDiscrete Applied Mathematics
Volume29
Issue number1
DOIs
StatePublished - Nov 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm'. Together they form a unique fingerprint.

Cite this