ENUMERATING INTERDISTANCES IN SPACE

In this paper, we study the enumerative versions of the interdistance ranking and selection problems in space, namely, the fixed-radius near neighbors and interdistance enumeration problems, respectively. The input to the fixed-radius near neighbors problem is a set of n points S subset of R-d and a nonnegative real number delta, and the output consists of all pairs of points within interdistance delta. We give an algorithm which, after an O(n log n) time preprocessing step, answers a fixed-radius near neighbors query with respect to an L-p metric in O(n + rho(delta)) time, where rho(delta) is the rank of delta. The space needed is O(n). The input to the interdistance enumeration problem is a set of n points S subset of R-d and an integer k, 1 <= k <= ((n)(2)), and the output is a set of point pairs, each corresponding to an interdistance having length less than or equal to the interdistance with rank k. We offer an O(n log n + k) time, O(n + k) space algorithm for this problem. This algorithm also works for any L-p metric.