An optimal algorithm for the angle-restricted all nearest neighbor problem on the reconfigurable mesh

Given a set S of n points in the plane and two directions r₁ and r₂, the angle-restricted all nearest neighbor problem (ARANN) asks to compute for every point p in S the nearest point in S lying in the planar region bounded by two rays in the directions r ₁ and r₂ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an arbitrary instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size n×n. Our algorithm is optimal in the sense that Ω(n²) processors are necessary to solve the ARANN problem in O(1) time