Accession Number:

ADA058280

Title:

A Note on Rabin's Nearest-Neighbor Algorithm.

Descriptive Note:

Technical rept.,

Corporate Author:

CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1978-01-01

Pagination or Media Count:

13.0

Abstract:

Rabin has proposed a probabilistic algorithm for finding the closest pair of a set of points in Euclidean space. His algorithm is asymptotically linear whereas the best of the known deterministic algorithms take order nlogn time. At least part of the speedup is due to the model rather than the probabilistic nature of the algorithm.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE