Shallow Interdistance Selection and Interdistance Enumeration

Author:Salowe, J, Department of Computer ScienceUniversity of Virginia

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 [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<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)
Source Citation:

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
Published Date: