An algorithm for approximate closest-point queries

ABSTRACT

This paper gives an algorithm for approximately solving the post office problem: given n points (called sites) in d dimensions, build a data structure so that, given a query point q, a closest site to q can be found quickly. The algorithm is also given a relative error bound &egr;, and depends on a ratio &rgr;, which is no more than the ratio of the distance between the farthest pair of sites to the distance between the closest pair of sites. The algorithm builds a data structure of size O(n&eegr;)O(1/&egr;)(d−1)/2 in time O(n2&eegr;)O(1/&egr;)(d−1). Here &eegr;=log(&rgr;/&egr;). With this data structure, a site is returned whose distance to a query point q is within 1+&egr; of the distance of the closest site. A query needs O(logn)O(1/&egr;)(d−1)/2 time, with high probability.

REFERENCES

• AM93: Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
• AMN+94: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
• AS90: I. Adler and R. Shamir. A randomization scheme for speeding up algorithms for linear and convex quadratic programming problems with a high constraintsto-variables ratio. Technical Report 21- 90, Rutgers Univ., May 1990. To appear in Math. Programming.
• Ber93: Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
• Cla88: K.L. Clarkson. ALas Vegas algorithm for linear programming when the dimension is small. In Proc. 29th IEEE Syrup. on Foundations of Computer Science, pages 452-456, 1988. Revised version: Las Vegas algorithms for linear and integer programming when the dimension is small (preprint).
• Cla93: Kenneth L. Clarkson, Algorithms for Polytope Covering and Approximation, Proceedings of the Third Workshop on Algorithms and Data Structures, p.246-252, August 11-13, 1993
• Dud74: R.M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approximation Theory, 10:227- 236, 1974.
• Pug90: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• Sen: S. Sen. Some oberservations on skip lists.
• Vai89: P.M. Vaidya. A new algorithm for minimizing convex functions over convex sets. In Proc. 30th Annu. IEEE $ympos. Found. Comput. Sci., pages 338-343, 1989.
• Yao82: A.C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11:721-736, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory