ENUMERATING INTERDISTANCES IN SPACE
- 1 March 1992
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 2 (1) , 49-59
- https://doi.org/10.1142/s0218195992000044
Abstract
In this paper, we study the enumerative versions of the interdistance in terdis stance ranking and selection problems in space, namely, the fixed-radius near neighbors and interdistance enumeration problems, respectively. The input to the fixed-radius near neighbors problem is a set of n points S⊆ℜd and a nonnegative real number δ, and the output consists of all pairs of points within interdistance δ. We give an algorithm which, after an O(n log n) time preprocessing step, answers a fixed-radius near neighbors query with respect to an Lp metric in O(n+ρ(δ)) time, where ρ(δ) is the rank of δ. The space needed is O(n). The input to the interdistance enumeration problem is a set of n points Sℜd and an integer k, , and the output is a set of point pairs, each corresponding to an interdistance having length less than or equal to the interdistance with rank k. We offer an O(n log n+k) time, O(n+k) space algorithm for this problem. This algorithm also works for any Lp metric.Keywords
This publication has 0 references indexed in Scilit: