Я думаю, что одна из причин, по которой у вас могут возникнуть проблемы с поиском бумаги, заключается в том, что в этом ответном документе Хопкрофта и Фортуны упоминаются некоторые проблемы с ним.В частности, алгоритм Рабина направлен на использование рандомизации для нахождения ближайших точек за O (n) времени, и хотя он правильно делает это, настоящая причина ускорения заключается в способности преобразовывать постоянные по времени из произвольных действительных чисел в их целые этажи.Исходя из этого предположения, Хопкрофт и Фортуна предлагают детерминированный алгоритм O (n lg lg n) для нахождения ближайших точек на плоскости.
Я не знаю, является ли это удовлетворительным ответом на ваш вопрос, но напо крайней мере, приведенная выше ссылка - крутой алгоритм!