A Note on Rabin's Nearest-Neighbor Algorithm.
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Statistics and Probability