FIXED-RADIUS NEAR NEIGHBORS SEARCH ALGORITHMS FOR POINTS AND SEGMENTS

The fixed-radius near neighbors search problem for points is as follows: Given a set S of n points on a plane and a search radius δ, find all pairs of points in S which are no further apart than δ. We present a new, and conceptually simple algorithm for this problem which compares favorably to the best previous algorithms of Bentley, Stanat and Williams and Cole and Yap. Although Shamos and Hoey conjectured that the Voronoi diagram has no means of dealing with general distance relationships such as this, our algorithm makes use of the Voronoi diagram as its basic data structure. The algorithm runs in O(n+I) time with an O(n log n) preprocessing phase where I is the number of pairs reported. We also generalize this algorithm to the fixed-radius search problem for segments. For this latter problem, we give an O(nθ+Iθ) algorithm with an O(nθ log(nθ)) preprocessing phase where θ is the ratio L/δ of the length L of the longest segment to the search distance δ. © 1990.