An Optimal Parallel Algorithm For the All Nearest - - Neighbor Problem for a Convex Polygon
Michael T. Goodrich · Purdue e-Pubs (Purdue University System) · 1985
In this paper we give a parallel algorithm for finding the nearest-neighbor vertex of each vertex of a convex polygon.Our algoritb..z::J.runs in O(log n) time using O(njlogn) processors, in the parallel computation model CREW PRA.lvr (Concurrent-Read, Exclusive-Write Parallel RAM).This implies that the all nearest-neighbors problem for a convex polygon can be solved in O(n/p+logn) time using p processors, which is optimal.