Efficient algorithms for the all nearest neighbor and closest pair problems on the linear array with a reconfigurable pipelined bus system

We present two O(1)-time algorithms for solving the 2D all nearest neighbor (2D_ANN) problem, the 2D closest pair (2D_CP) problem, the 3D all nearest neighbor (3D_ANN) problem and the 3D-closest pair (3D_CP) problem of n points on the linear array with a reconfigurable pipelined bus system (LARPBS) from the computational geometry perspective. The first O(1) time algorithm, which invokes the ANN properties (introduced in this paper) only once, can solve the 2D_ANN and 2D_CP problems of n points on an LARPBS of size 1/2n⁵3+c/, and the 3D_ANN and 3D_CP problems pf n points on an LARPBS of size 1/2n⁷4+c/, where 0 < ε = 1/2^c+1-1 ≪ 1, c is a constant and positive integer. The second O(1) time algorithm, which recursively invokes the ANN properties k times, can solve the kD_ANN, and kD_CP problems of n points on an LARPBS of size 1/2n³2+c/, where k = 2 or 3, 0 < ε = 1/2ⁿ⁺¹-1 ≪ 1, and c is a constant and positive integer. To the best of our knowledge, all results derived above are the best O(1) time ANN algorithms known.