Shallow Interdistance Selection and Interdistance EnumerationReport
Shallow interdistance selection refers to the problem of selecting the k<sup>th</sup> smallest interdistance, k <= n, from among the (n choose 2) interdistances determined by a set of n points in ℜ<sup>d</sup>. 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 ). 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. ). We give a shallow interdistance selection algorithm which takes optimal O(n log n) time and works in any L<sub>p</sub> 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)).
All rights reserved (no additional license for public reuse)
Salowe, J. "Shallow Interdistance Selection and Interdistance Enumeration." University of Virginia Dept. of Computer Science Tech Report (1991).
University of Virginia, Department of Computer Science