[알고리즘] 최근접 점의 쌍 찾기

---

최근접 점의 쌍(Closest pair)은 평면 위에서 n개의 점이 있을 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제이다.

 

이 문제를 효율적으로 해결하는 방법은 분할 정복을 이용하는 것이다. n개의 점을 1/2로 분할하여 각 부분문제에서 최근접 점의 쌍을 찾고, 2개의 결과값 중에서 짧은 거리를 갖는 쌍을 찾는다. 

 

알고리즘)

function ClosestPair(S)
input : x좌표가 오름차 순으로 정렬된 배열 S(원소의 개수는 i)
output :  S에서 가장 가까운 점들의 거리

1. if(i<=3) return 거리
2. 정렬된 S를 1/2 씩 분할한다. 단, S가 홀수이면 왼쪽 배열에 1개 원소를 더 준다.
3. CP1 = ClosestPair(S1) //CP1은 왼쪽 배열에서 최근접 점의 쌍이다.
4. CP2 = ClosestPair(S2) //CP2는 오른쪽 배열에서 최근접 점의 쌍이다.
5. d = min{dist(CP1), dist(CP2)}일 때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾아서 
CP3이라고 한다. 
6. return(CP1, CP2, CP3 중에서 거리가 가장 짧은 쌍)