A neighbor-finding algorithm for bincode-based images on reconfigurable meshes

Using bincodes to represent binary images is a storage-saving encoding scheme. Finding neighbors is one of the most important operations in spatial data structures. This paper presents an efficient parallel algorithm for solving the problem of neighbor-finding for a bincode-based binary image. Given a set of the bincodes of n blocks, the neighbor-finding algorithm can be accomplished in O(1)-time on an n(1/2) x n(1/2) x n(1/2) reconfigurable mesh. Under the same time bound, i.e. constant time, the number of processors used in the proposed parallel algorithm is O(n(3/2)) and is less than that of the previous fastest one on a mesh with multiple broadcasting buses [1] which needs O(n(2)) processors.