그래서 저는 O (n) 시간에 2D에서 점들의 집합이 주어진 가장 가까운 이웃을 찾는 Michael Rabin의 알고리즘에 대한 세부 사항을 찾으려고합니다. 웬일인지, Google 검색은 나를 완전히 실패하고있다. 내가 찾은 최선의 설명은 여기에 있습니다 : http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/. 사람이에 대해 아무것도 알고, 어디서 (바람직하게 온라인으로!) 주제에 책이나 종이를 찾을 수, 난 정말 당신이 무게 감사하겠습니다 알고있는 경우라빈의 가장 가까운 이웃 (가장 가까운 점 쌍) 알고리즘?
.
나는 이유 중 하나가 당신이 수도 생각 그 문제를 언급 한 this response paper by Hopcroft and Fortune 때문에 신문을 찾는 데 어려움을 겪고있는 것입니다. 특히, Rabin의 알고리즘은 O (n) 시간에 가장 가까운 점을 찾기 위해 무작위 추출을 사용하는 것으로 알려져 있으며, 올바르게 수행하는 동안 속도 향상의 실제 이유는 임의의 실수에서 정수형 바닥으로의 일정 시간 변환을 수행하는 기능입니다. 이 가정에서, Hopcroft와 Fortune은 비행기에서 가장 가까운 점을 찾기위한 결정 론적 O (ngg lg n) 알고리즘을 제안합니다.
이 질문에 대한 만족스러운 답변인지는 모르지만 최소한 위의 링크는 멋진 알고리즘입니다.
"가장 가까운 이웃"은 진절머리 나는 이름이었습니다. 이것은 가장 단순한 포인트 문제 쌍으로 더 잘 알려져 있습니다. 예를 들어, http://en.wikipedia.org/wiki/Closest_pair_of_points_problem은 Khuller와 Matias의 단순화를 인용합니다. http://www.cs.umd.edu/~samir/grant/cp.pdf
1976 년 "알고리즘 및 복잡성"에 처음 게시되었습니다. 그것의 온라인 버전 일 수 있습니다. –