FAST NEAREST NEIGHBOR ALGORITHMS ON A LINEAR ARRAY WITH A RECONFIGURABLE PIPELINED BUS SYSTEM
Yi Pan, Keqin Li, Si-Qing Zheng · International Journal of Parallel Emergent and Distributed Systems · 1998
We present efficient algorithms for the nearest neighbor problem defined in an n × 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(loglogn) time, and using an LARPBS of n2+∊ processors, for any fixed constant ∊>0. the nearest neighbor problem can be solved in O(l) 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.