A Time-Optimal Multiple-Query Nearest-Neighbour Algorithm on Meshes with Multiple Broadcasting

摘要

The multiple-query nearest-neighbor (MQNN) problem is stated as follows: given a set 5 of n points in plane and a set Q of m(1 ≤ m ≤ n) query points, determine for every point in Q its closest neighbor in S. Besides the pure theoretical interest, this problem has many practical applications in various areas such as: computer graphics, pattern recognition and image processing. First, this paper proposes a new time-optimal algorithm to solve the all nearest-neighbor (ANN) problem in O(n~(1/2)) time on a mesh-connected computer of size n~(1/2) x n~(1/2). Next, using this result in conjunction with the generalized multiple search (GMS) paradigm of Bokka et al. we devise a time-optimal algorithm that solves the MQNN problem in O(n~(1/6)m~(1/3)) time on a mesh with multiple broadcasting (MMB) of size n~(1/2) x n~(1/2).