Fast Algorithms for Approximating Distances
Abstract:
Let S be a set of n points in the plane and let 1
\leq k \leq n(n1)/2. Let d_1 \leq d_2 \leq ... \leq d _{(n
choose 2)} be the L_{p}distances determined by
the pairs of points in S.
In this paper we consider the following optimization problems:

Distance selection.
Compute the kth smallest distance between a pair of points of
S.
 Distance ranking.
Determine how many pair of points are closer than unit distance apart.
 Distance by query.
Preprocess S into a data structure, so that, given a number
k as above, one can answer efficiently what is the kth
smallest distance between a pair of points of S.
We present algorithms for approximate distance selection with running time
O(n lg^{3}n)
(in contrast with the best known
O(n^{4/3}polylogn) randomized algorithm for the exact
problem). We also provide efficient approximation algorithms for distance
ranking and distance queries.
@article{bsfaad02
, author = "S. Bespamyatnikh and M. Segal"
, title = "Fast Algorithms for Approximating Distances"
, journal = "Algorithmica"
, year = 2002
, volume = 33
, number = 2
, pages = "263269"
}
