Fast Algorithms for Approximating Distances
Abstract:
Let S be a set of n points in the plane and let 1
\leq k \leq n(n-1)/2. Let d_1 \leq d_2 \leq ... \leq d (n
choose 2) be the Lp-distances determined by
the pairs of points in S.
In this paper we consider the following optimization problems:
-
Distance selection.
Compute the k-th 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 k-th
smallest distance between a pair of points of S.
We present algorithms for approximate distance selection with running time
O(n lg3n)
(in contrast with the best known
O(n4/3polylogn) randomized algorithm for the exact
problem). We also provide efficient approximation algorithms for distance
ranking and distance queries.
@article{bs-faad-02
, author = "S. Bespamyatnikh and M. Segal"
, title = "Fast Algorithms for Approximating Distances"
, journal = "Algorithmica"
, year = 2002
, volume = 33
, number = 2
, pages = "263--269"
}
|