최근접 점쌍 문제 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Closest pair of points.svg|150px|right|thumb|최근접 점쌍이 빨간색으로 표시되어있다.]]

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

가능한 모든 점쌍들의 거리를 비교해 최솟값을 찾는 알고리즘은 [[점근 표기법|O]](''n''<sup>2</sup>)의 시간을 요구한다. 하지만 [[유클리드 공간]]이나 정해진 d의 차원을 가지는 [[Lp 공간|L<sup>p</sup> 공간]]에서는 O(''n'' log ''n'')의 시간에 해결 될 수 있다.

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

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

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

{{전거 통제}}
{{토막글|컴퓨터 과학}}

[[분류:기하 알고리즘]]