Item Details

Shallow Interdistance Selection and Interdistance Enumeration

Salowe, J
Salowe, J
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)).
University of Virginia, Department of Computer Science, 1991
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online