A Note on Rabin's Nearest-Neighbor Algorithm.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1978
Accession Number
ADA058280

Entities

People

  • John Hopcroft
  • Steve Fortune

Organizations

  • Department of Computer Science, Cornell University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Arithmetic
  • Computer Science
  • Computers
  • Intervals
  • Iterations
  • Lists (Data Structures)
  • Mathematics
  • Numbers
  • Observation
  • Real Numbers
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.
  • Neural Network Machine Learning.

Technology Areas

  • Space