최근접 점 쌍 계산기(분할정복)

x좌표로 점들을 반씩 나눈 뒤, 왼쪽·오른쪽에서 각각 재귀적으로 최근접 쌍을 구합니다. 두 결과 중 작은 거리를 d라 하면, 경계선에서 d 이내의 좁은 띠 안에 있는 점들만 다시 살펴봐 더 가까운 쌍이 있는지 확인합니다.

띠를 y좌표 순으로 정렬해 훑으면, 한 점이 비교해야 할 상대는 y좌표 차이가 d 미만인 몇 개뿐이라는 것이 기하학적으로 증명됩니다. 이미 왼쪽·오른쪽 각각에서 d 미만으로 가까운 점이 없다고 확인했으므로, 같은 쪽에 점이 그보다 촘촘하게 몰려 있을 수 없기 때문입니다.

모든 점 쌍을 다 비교하면 점이 n개일 때 약 n²/2번의 거리 계산이 필요합니다. 분할정복은 이를 O(n log n)으로 줄입니다. 점이 1000개면 브루트포스는 약 50만 번, 분할정복은 약 1만 번 정도의 비교로 끝나는 큰 차이입니다.

kd-tree는 "이 질의점에 가장 가까운 저장된 점은 무엇인가"를 반복해서 물을 때 유용한 자료구조입니다. 최근접 점 쌍 알고리즘은 저장된 점들 자체 중에서 가장 가까운 두 점을 한 번에 찾는 별개의 문제로, 질의를 반복하지 않는 일회성 계산입니다.