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"
}