A Time-Optimal All-Nearest Neighbor Algorithm on Meshes with Multiple Broadcasting
Stephan Olariu, Ivan Stojmenović · 1993
The All-Nearest Neighbor problem (ANN, for short) is stated as follows: given a set S of points in the plane, determine for every point in S, a point that lies closest to it. The ANN problem is central in VLSI design, computer graphics, pattern recognition, and image processing, among others. In this paper we propose a time-optional algorithm to solve the Ann problem on meshes with multiple broadcasting. For this purpose, we first establish an ( )(log n) time lower bound for the task of solving an arbitrary n-point instance of the ANN problem. This lower bound holds for both the CREW-PRAM and for the mesh with multiple broadcasting. Next, we show that the bound is tight by exhibiting an algorithm solving the problem in O(log n) time on a mesh with multiple broadcasting of size n x n.