Fast nearest neighbor algorithms on a linear array with a reconfigurable pipelined bus system. - Pan, Yi (Parallel algorithms and applications.)
We present efficient algorithms for the nearest neighbor problem defined in an n x n binary image. We show that using a linear array with a reconfigurable pipelined bus system (LARPBS) of n2 processors, the nearest neighbor problem can be solved in O (log log n) time, and using an LARPBS of n 2+e processors, for any fixed constant e > 0, the nearest neighbor problem can be solved in O(1) time. We also show that the nearest neighbor problem can be solved on an LARPBS of n2 processors in O (1) time with high probability.