Item Details

Shallow Interdistance Selection and Interdistance Enumeration

Salowe, J
Format
Report
Author
Salowe, J
Abstract
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)).
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1991
Published Date
1991
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online