Shallow Interdistance Selection and Interdistance Enumeration

Shallow interdistance selection refers to the problem of selecting the k^th smallest interdistance, k <= n, from among the (n choose 2) interdistances determined by a set of n points in ℜ^d. Shallow interdistance selection has a concrete application -- it is a crucial component in the design of a data structure that dynamically maintains the minimum interdistance in O(sqrt n log n) time per operation (Smid [6]). In addition, the study of shallow interdistance selection may provide insight into developing more efficient algorithms for the problem of selecting Euclidean distances (Agarwal er al. [1]). We give a shallow interdistance selection algorithm which takes optimal O(n log n) time and works in any L_p metric. To do this, we prove two interesting related results. The first is a combinatorial result relating the rank of x to the rank of 2x The second is an algorithm which enumerates all pairs of points within interdistance x in time proportional to the rank of x (plus O(n log n)).

Salowe, J. "Shallow Interdistance Selection and Interdistance Enumeration." University of Virginia Dept. of Computer Science Tech Report (1991).