Algorithm.ClosestPair Theory

[Visual Studio과 C#으로 구현/분할정복]
Algorithm ClosestPair Coding // Week05

20211007_20615034

ClosestPair Coding_Theory

ClosestPair Coding이란 최근접 점의 쌍 찾기 코딩이다.

[최근접 점의 쌍(Closest Pair) 찾기]

: 최근접 점의 쌍(Closest Pair) 문제는 2차원 평면상의 n개의 점 이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제.

[최근접 점의 쌍 찾기]

> 간단한 방법

 • 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는다. 

 • 예를 들어, 5개의 점이 아래의 [그림]처럼 주어지면, 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5 사이의 거리를 각각 계산하여 그 중에 최소 거리를 가진 쌍이 최근접 점의 쌍이 되는 것이다. 

[O(n2)보다 효율적인 분할 정복 이용]

 • n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고,

   2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾는다.

 • 그리고 2개의 부분해를 취합할 때에는 반드시 다음과 같은 경우를 고려해야 한다.

 • 왼쪽 부분 문제의 최근접 쌍의 거리가 10이고, 오른쪽 부분 문제의 최 근접 쌍의 거리가 15이다.

 • 왼쪽 부분 문제의 가장 오른쪽 점과 오른쪽 부분 문제의 가장 왼쪽 점 사이의 거리가 7이다.

 • 따라서 2개의 부분 문제의 해를 취합할 때 단순히 10과 15 중에서 짧 은 거리인 10을 해라고 할 수 없는 것이다.

 • 그러므로 아래의 그림에서와 같이 각각 거리가 10이내의 중간 영역 안에 있는 점들 중에 최근접 점의 쌍이 있는지도 확인해보아야 한다.

[최근접 점의 쌍 분할 정복 알고리즘]