A Parallel Algorithm for k-Nearest-Neighbor on Reconfigurable Meshes

Nearest neighbor query is a basic problem of computational geometry As an extension of nearest neighbor query, k nearest neighbor is widely applied in the fields of VLSI design, data retrieval, pattern matching, graph processing, etc A parallel algorithm on a reconfigurable mesh of size N×N for k nearest neighbor search in a planar point set S of N points is presented The time complexity of this algorithm is O（k） It attains the lower bound of this problem