최근접 점쌍 문제

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

최근접 점쌍이 빨간색으로 표시되어있다.

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

완전 탐색 알고리즘

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

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)안에 해결할 수 있다.

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

다른 점은 (d*2d)크기의 직사각형 안에 존재해야 한다.

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