최근접 점쌍 문제

최근접 점쌍 문제 (closest pair problem)는 계산기하학의 문제로서, 거리 공간상에 n 개의 점이 주어졌을 때, 사이의 거리가 가장 짧은 두 점을 찾아내는 문제이다.

가능한 모든 점쌍들의 거리를 비교해 최솟값을 찾는 알고리즘은 O(n2)의 시간을 요구한다. 하지만 유클리드 공간이나 정해진 d의 차원을 가지는 Lp 공간에서는 O(n log n)의 시간에 해결 될 수 있다.

완전 탐색 알고리즘 
최근접 점쌍은 완전 탐색 알고리즘을 사용하면 O(n2)의 시간에 찾을 수 있다.
이를 위해서는 아래와 같이 개의 모든 쌍들 사이의 거리를 계산하여 그 중 가장 가까운 두 점을 고르면 된다.

 minDist = infinity
 for i = 1 to length(P) - 1
  for j = i + 1 to length(P)
   let p = P[i], q = P[j]
   if dist(p, q) < minDist:
    minDist = dist(p, q)
    closestPair = (p, q)
 return closestPair

좌표 평면 
점들이 좌표 평면에 주어질 경우, 이 문제는 다음과 같은 재귀적인 분할 정복 알고리즘으로 O(n log n)안에 해결할 수 있다.

점들을 x좌표에 따라 오름차순으로 정렬한다.
점들이 두개의 같은 크기의 집합으로 나뉘도록 수직선 을 기준으로 양옆으로 분할한다.
왼쪽과 오른쪽의 점들의 집합에 대해 재귀적으로 문제를 해결한다. 이것을 통해 왼쪽과 오른쪽에서의 최근접 거리인  와 을 찾을 수 있다.
하나의 점은 분할선 왼쪽에 존재하고, 다른 점은 분할선 오른쪽에 존재하는 쌍들 중 그 거리가 최소가 되는 쌍을 찾는다. 이것을 통해 을 찾을 수 있다.
최종적으로 찾고자 하는 최근접 거리는  중 가장 짧은 거리이다.

4번째 단계를 해결할 때 가능한 모든 쌍들을 탐색 해 본다면, 역시 제곱에 비례하는 시간이 필요할 것이다. 하지만 점들이 분포되어있는 특별한 성질을 이용한다면, 선형적 시간안에 해결될 수 있다. 3번 단계를 통해서, 가장 가까운 두 점은 보다 더 멀리 떨어져 있을 수는 없음을 알 수 있다. 따라서 분할선 왼쪽에 있는 각각의 점 에 대해서, 의 좌표를 중심으로 하고 분할선 오른쪽에 존재하는  크기의 직사각형 내부에 존재하는 점들에 대해서만 거리를 계산해도 된다. 이 직사각형은 최대 6개까지의 점만을 포함하기 때문에, 최대  쌍의 점들에 대해서만 계산을 해도 충분히 최소 거리를 구할 수 있다. 이 알고리즘의 연산의 수행 횟수를 재귀식을 표현하면 으로 표현할 수 있으며, 마스터 정리에 따라 로 나타낼 수 있다.

기하 알고리즘