¿El vecino más cercano de Rabin (par de puntos más cercano) algoritmo?

Question

Así que estoy tratando de encontrar detalles sobre un algoritmo de Michael Rabin, que encuentra al vecino más cercano, dado un conjunto de puntos en 2D en O (n) tiempo.Por alguna razón, la búsqueda de Google está completamente fallando.La mejor (y única) descripción que he encontrado está aquí: >http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ .

Si alguien sabe algo sobre esto, o sabe dónde encontrar un libro o un papel sobre el tema (¡preferiblemente en línea!), Realmente apreciaría que te peses.

Answer 1

Creo que una de las razones por las que podría estar teniendo problemas para encontrar el papel es debido a este artículo de respuesta de Hopcroft y Fortune mencionando algunos problemas con él.En particular, el algoritmo de Rabin se pretende utilizar la aleatorización para encontrar puntos más cercanos en el tiempo de O (n), y mientras hace correctamente la verdadera razón para la aceleración es la capacidad de hacer conversiones de tiempo constante de los números reales arbitrarios a sus pisos de enteros.Con este supuesto, Hopcroft y Fortune proponen un algoritmo determinista O (n LG LG N) para encontrar puntos más cercanos en el plano.

No sé si esta es una respuesta satisfactoria a su pregunta, pero al menos el enlace anterior es un algoritmo fresco!

Answer 2

"Vecino más cercano" fue un nombre de mierda.Es mejor conocido como el "problema de par de puntos más cercano", por ejemplo, http://en.wikipedia.org/wiki / clostr_pair_of_points_problem , que cita esta simplificación de Khuller y Matias: http://www.cs.umd.edu/~samir/grant/cp.pdf