최근접점쌍 문제는 간단하게 말해, 주어진 점들 중 가장 가까운 두 점을 찾는 문제입니다.
예를 들어 (8, 8), (10, 15), (5, 15), (20, 3), (9, 7), (15, 9), (8, 15), (20, 14), (17, 13), (16, 11), (7, 12), (10, 10), (1, 19), (30, 9), (22, 4), (6, 1) 의 점들이 있을때 알고리즘을 이용하여 최근접점쌍을 찾는 과정은 다음과 같습니다.
먼저, 점들의 x 좌표와 y 좌표를 이용해 정렬합니다. 분할해서 문제를 해결하기 때문입니다.
점들을 정렬하고 나면 다음 알고리즘을 수행합니다.
분할 할 때 남아있는 점이 3개 미만일 때까지 분할하기 때문에 나누다보면 위의 그림처럼 각 부분에서 점이 2개씩 존재하게 되는 것 입니다.
분할한 부분의 점의 개수가 3개 미만이 될 경우, 각 점들 사이의 거리를 계산합니다. 점들의 거리 계산은 보통 수학에서 사용하는 점들 사이의 거리 식을 이용합니다. 거리를 구했다면 가장 가까운 점들의 쌍을 반환합니다.
또한 중간영역 최근접점의 상 구하기라는 부분에서는 (첫번째 그림 상에서) SL11 영역의 가장 오른쪽 점과 SL12영역의 가장 왼쪽 점의 거리를 비교했을 때 더 짧은 거리가 나올 수 있기 때문에 수행하는 과정입니다. 분할해서 다른 영역이 되어버렸지만 점의 거리가 더 짧을 수도 있습니다.
위의 표는 SL1의 점들의 거리비교를 한 것입니다. d는 중간 영역 최근접 점의 쌍을 구하기 전 각 세부영역의 점들의 거리를 계산해서 나온 가장 작은 거리의 수입니다. 현재 가장 가까운 점들의 거리가 5이므로 x좌표의 값을 비교하여 차이가 5이상이면 계산할 필요도 없으므로(어차피 더 거리가 크게 나옴) 제외하기 위해서 사용합니다. 표에서 SL11 영역의 가장 오른쪽 점과 SL12영역의 가장 왼쪽 점을 기준으로 x좌표가 5이상 차이나면 계산에서 제외하지만 5이상 차이나는 점이 없으므로 모든 점들과 거리를 계산해봐야 합니다.
그래서 나온 SL1영역에서의 최근접 점의 쌍은 (5,15), (7,12)이며 거리는 3입니다. 다른 영역도 같은 방법으로 구하면 됩니다.
* 참고한 책 : 3장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사
** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.
***최근접점쌍 문제의 경우 순서쌍만 제시하기때문에 교수님이 과제로 내주신 문제(순서쌍)를 그대로 사용하였으며 그림 및 알고리즘 과정은 제가 작성하였습니다.