Алгоритм ближайшего соседа Рабина (ближайшая пара точек)?
Поэтому я пытаюсь найти подробности об алгоритме Майкла Рабина, который находит ближайшего соседа по заданному набору точек в 2D за O(n) времени. По какой-то причине поиск в Google полностью провалился. Лучшее (и единственное) описание, которое я нашел, находится здесь: http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/.
Если кто-нибудь что-нибудь знает об этом или знает, где найти книгу или статью по этому вопросу (желательно онлайн!), Я был бы очень признателен, если бы вы взвесили.
2 ответа
Я думаю, что одна из причин, по которой у вас могут возникнуть проблемы с поиском бумаги, заключается в том, что в ответном документе Хопкрофта и Фортуны упоминаются некоторые проблемы с ним. В частности, алгоритм Рабина направлен на использование рандомизации для нахождения ближайших точек за O(n) времени, и, хотя он правильно делает это, настоящая причина ускорения заключается в способности преобразовывать постоянное время из произвольных действительных чисел в их целые этажи. Исходя из этого предположения, Хопкрофт и Фортуна предлагают детерминистический алгоритм O(n lg lg n) для нахождения ближайших точек на плоскости.
Я не знаю, является ли это удовлетворительным ответом на ваш вопрос, но по крайней мере приведенная выше ссылка является классным алгоритмом!
"Ближайший сосед" - дерьмовое имя. Она более известна как "проблема ближайших парных точек", например, http://en.wikipedia.org/wiki/Closest_pair_of_points_problem, которая цитирует это упрощение Хуллера и Матиаса: http://www.cs.umd.edu/~samir/grant/cp.pdf