13. closest pair [6 1주차]

13. Closest Pair [6-1주차]

2024년 1월 13일 토요일

오후 10:45

<Closest Pair>

점들의 좌표가 주어지고, 가장 가까운 두 점을 찾아내는 문제이다.

거리는 식 {(x₁ - x₂)² + (y₁ - y₂)²}^1/2 를 이용해 구함.

 

모든 쌍을 확인하는 방법으로 풀면 _nC₂, O(n²) 의 시간이 걸린다.

O(nlogn)으로 문제를 푸는 방법을 알아보자.

 

좌표가 1차원인 경우 : 정렬을 한 후 거리를 재면 된다. 1차원도 O(nlogn) 보다 빠르게 풀 순 없다.

 

2차원의 경우를 divide and conquer를 이용해 풀 수 있다.

 

 

<divide and conquer를 이용한 풀이 아이디어>

x좌표로 정렬한 후 점들을 절반으로 나눈다. (정렬은 재귀 호출 시에는 안 해도 된다)

왼쪽에서의 가장 가까운 쌍과 오른쪽에서의 가장 가까운 쌍을 찾는다.

그 두 쌍과 왼쪽과 오른쪽에서 하나씩을 뽑은 쌍을 비교하면 될 것이다.

-> 왼쪽과 오른쪽에서 하나씩 뽑은 쌍을 비교하는 데 n/2 * n/2 = O(n²) 시간이 걸림.

-> 더 빠르게 해야 한다.

 

 

<분할정복을 이용한 Closest Pair>

모든 점들의 집합을 Q라고 한다.

알고리즘의 각 재귀 호출은 입력으로 Q의 부분 집합 P, 배열 X, 배열 Y를 받는다.

 

X와 Y는 P의 모든 점으로 구성되며, X는 x좌표 기준으로 오름차순 정렬, Y는 y좌표 기준으로 오름차순으로 정렬할 것이다.

 

P의 원소 개수가 3이하이면, _nC₂ 가지 쌍을 모두 조사한다.

원소 개수가 3을 초과하면, 다음 분할정복 모델을 실행한다.

 

1.     분할

P를 P_L 과 P_R로 이등분하는 수직선 L을 찾는다. P_L의 점들은 수직선 왼쪽, P_R의 점들은 수직선 오른쪽에 있다.

배열 X도 X_L과 X_R로 분할한 뒤, 각각 x좌표에 대해 오름차순 정렬한다.

배열 Y는 Y_L과 Y_R로 분할한 뒤, 각각 y좌표에 대해 오름차순 정렬한다.

 

2.     정복

P_L과 P_R에 대해 재귀 호출한다.

ClosestPair(P_L , X_L , Y_L), ClosestPair(P_R , X_R , Y_R)

이를 통해, P_L 내의 가장 가까운 쌍 c_L과

P_R 내의 가장 가까운 쌍 c_R을 얻는다.

c = min(c_L, c_R) 이라 한다.

 

3.     결합

가장 가까운 쌍은 c 이거나, 한 점은 P_L, 다른 한 점은 P_R에 있는 쌍이다.

거리가 c보다 작은 쌍이 존재한다면, 두 점은 직선 L에서 거리 c 이내에 존재해야 한다.

따라서 두 점은 L을 중심으로 하는 2c 너비의 영역 안에 존재한다.

영역 안에 쌍이 존재한다면, 다음 작업을 수행한다.

 

a.     배열 Y에서 2c 너비의 영역 안에 있지 않은 점들을 제거해 배열 Y' 을 만든다.

Y'도 y축으로 정렬된 상태이다.

b.     Y'의 각 점 p에 대해, p위의 7개 점

(Y'에 있고, y좌표 기준 바로 위의 7개 점)

까지의 거리를 각각 계산한다.

이렇게 구한 거리 중 가장 가까운 것을 구하고, c'이라 한다.

7개 점하고만 비교해도 되는 근거는 곧 증명할 것이다.

c.      min(c, c') 을 리턴한다.

 

 

<Closest Pair 알고리즘 정확성>

Y'의 있는 각 점 p에 대해서, p 위의 7개 점만 조사하면 된다는 것을 증명해 보자.

 

P_L의 원소 p_L과 P_R의 원소 p_R 쌍의 거리 c'이 가장 작다고 가정하자.

c' < c 가 성립한다.

 

따라서 두 점은 직선 L에 중심을 둔 가로2c * 세로c 영역의 직사각형 영역 안에 들어갈 수 있다. 이 직사각형은 L에 의해 두 정사각형으로 나뉜다.

 

왼쪽 정사각형에 있는 점들은 거리가 c이상이여야 하므로, 정사각형 안에 최대 4개의 점이 들어갈 수 있다. (정사각형의 4개의 꼭짓점에 점이 위치한 경우)

오른쪽 정사각형도 마찬가지로 최대 4개의 점이 들어갈 수 있다.

 

따라서 2c * c 의 직사각형 영역에는 최대 8개의 점이 들어갈 수 있다.

 

배열 Y' 에서 p_L이 p_R보다 먼저 나타난다고 가정하자.

직사각형에 최대 8개의 점이 존재할 수 있으므로, p_R이 아무리 늦게 나와도 p_L뒤의 7칸 이내에 나오게 된다.

 

 

<구현과 수행시간>

절반씩 나뉘므로, 재귀 호출의 깊이는 logN이다.

따라서 O(NlogN) 시간 안에 알고리즘을 수행하려면, 각 재귀 호출에서 선형 시간 이하가 걸려야 한다.

 

첫 번째 재귀 호출을 하기 전에, 점들을 x좌표 기준으로 정렬한다. -> O(NlogN)

이 정렬된 배열을 재귀 호출을 할 때마다 절반으로 나누면 배열X를 얻을 수 있다.

 

배열 Y는 Merge Sort의 과정을 이용하여 구할 수 있다.

두 재귀 호출의 결과로 Y_L과 Y_R을 얻은 뒤, 두 배열을 Merge하면 y좌표로 정렬된 배열 Y를 얻는다. 이는 O(n)의 시간이 걸린다.

 

 

<Plain Sweeping을 이용한 Closest Pair>

점들 전체를 X축 기준으로 정렬한다.

 

왼쪽의 수직선을 오른쪽으로 이동시킨다.

직선의 왼쪽 점들에 대해 Closest Pair c가 구해졌다고 가정한다.

 

수직선이 새로운 점 p를 만났다. 수직선 왼쪽의 점들 중 p와 가장 가까운 점과의 거리가 c'이라면, 새로운 Closest Pair는 min(c, c') 이다.

 

 

c'<= c인 경우, c' 쌍은 너비가 c, 높이가 2c이고 오른쪽 변의 중심이 p에 있는 직사각형 안에 있다. 따라서 수직선과 c이하로 떨어져있는 왼쪽 점들의 집합 P'중에서, p아래의 3개, 위의 3개 점만 확인하면 된다.

 

• 위아래 6개 점을 찾는 방법

수직선과의 거리가 c이하인 점들을 y좌표 기준 AVL트리에 넣는다. 이진 탐색을 통해 위아래 6개 점을 찾을 수 있다.

수직선이 다음 점 p2를 만났을 때, 새로운 직사각형의 너비 c2는 c보다 작으므로, AVL트리에 삭제 연산만 하면 된다. 단, p는 삽입해야 함.