An efficient O(1) time 3D all nearest neighbor algorithm from image processing perspective

In this paper, we solve the k-dimensional all nearest neighbor (kD_ANN) problem, where k=2 or 3, on a linear array with a reconfigurable pipelined bus system (LARPBS) from image processing perspective. First, for a two-dimensional (2D) binary image of size N×N, we devise an algorithm for solving the 2D_ANN problem using a LARPBS of size N2+ϵ, where 0<ϵ⪡1. Then, for a three-dimensional (3D) binary image of size N×N×N, we devise an algorithm for solving the 3D_ANN problem using a LARPBS of size N3+ɛ, where 0<ɛ<1. To the best of our knowledge, all results derived above are the best O(1) time 2D_ANN and 3D_ANN algorithms on the LARPBS model known.