Parallel algorithms for all nearest neighbors of binary images on the BSP model
Takashi Ishimizu, Akira Fujiwara, I. Inoue, Toshimitsu Masuzawa, Hideo Fujiwara · 2003
We present two parallel algorithms for computing the nearest neighbors of an n/spl times/n binary image on the Bulk-Synchronous Parallel (BSP) model. The first algorithm is for weighted distance, and the second algorithm is for L/sub p/ distance. Both algorithms run in O(n/sup 2//p+L) computation time and O(g/sup n///spl radic/p+L) communication time using p (1/spl les/p/spl les/n) processors and in O(n/sup 2//p+(d+L)log p/n/log(d+1)) computation time and in O(gn//spl radic/p+(gd+L)log p/n/log(d+1)) communication time using p (n