Plane Sweeping
지난 번에 배운 Closest Pair를 다른 technique으로 풀어보자(D&C 아님). 사실 이게 더 많이 쓰는 테크닉이다. 시간은 똑같이 O(NlogN)임.
이름 그대로 평면을 훑는 방법인데, 직관적으로 얘기하자면 (왼쪽에서 시작한다 가정했을 때) 직선을 오른쪽으로 밀면서 평면을 훑겠다는 것이다.
이걸 어떻게 구현할까? 실제로 구현할 때는 직선이 가장 왼쪽 끝점에서 시작해 다음 점으로 jump한다(이러기 위해서는 점들이 X좌표에 대해 정렬된 상태여야 한다). 총 N개의 직선을 순서대로 그리게 된다.
직선 안에 어떤 자료구조가 저장되어 있다고 생각해보자.
한 점에 도착했을 때, 왼쪽의 점들에 이 문제를 풀기 위해 필요한 정보가 어떤 자료구조로 저장되어 있다.
왼쪽 점들에서의 최소 거리 d를 저장하자.
다음 점으로 이동해보자.
재귀적(혹은 수학적 귀납법)으로 지금껏 본 점들만 생각해서는 답을 찾았다고 생각할 수 있다. 그리고 d는 재귀적으로 계산되어 있다고 믿으면 된다.
최소 거리가 d라고 하면 sweep하는 직선으로부터 왼쪽으로 거리가 d만큼 떨어진 직선을 하나 그어 band를 만들자. 그리고 band 내에 속하는 점들을 Y좌표에 대해 정렬해 balanced binary tree에 저장한다.
이 상태에서 직선을 다음 점으로 이동시킨다. 이때 band도 똑같이 움직이므로 band에 더이상 속하지 않는 점이 생긴다.
점들은 X 좌표에 대해 정렬되어 있으므로 순서대로 빠지면 된다. balanced binary tree는 logN시간에 insert/search/delete가 가능하므로 이 과정은 logN시간이 걸린다.
이제 d를 업데이트한다. 지난번에 closest pair를 구할 때와 동일한 방식으로 구하면 된다. 현재 점의 좌표를 (X, Y)라 하면 점의 위, 아래로 길이가 d인 정사각형을 그린다. 그리고 정사각형 내부의 점들(최대 5개)과의 거리를 계산해 더 작은 값이 나올 경우 d를 갱신한다. band에 속하는 점들은 Y좌표를 기준으로 tree에 sort되어 있으므로 [Y-d, Y+d] 범위의 점들을 구하는 것은 어렵지 않다.
binary tree에서 특정 범위의 값들을 찾는 과정은 어렵지 않고 이미 방법이 있다. 점들의 개수*logN시간이 걸리는데 점들이 최대 5개 있으므로 최대 5logN 시간이 걸린다.
d값이 갱신되면 band의 폭을 변화시킨 후 다음 점으로 이동하고, 그렇지 않다면 그냥 다음 점으로 이동한다. 이 과정을 마지막 점에 도착할 때까지 반복한다.
Wrap up
- 점들을 X좌표에 대해 정렬한다.
NlogN - 왼쪽 점부터 순서대로
N - 현재까지 본 점 중 가장 오른쪽 폭 d인 band 내의 점들이 Y좌표에 대해 정렬되어 balanced binary tree에 저장되어 있다.
NlogN- 새 직선을 긋는 과정은 logN 시간 내에 할 수 있다.
- 그러나 band에서 점이 여러 개 제거될 수 있으므로 한 칸을 넘을 때는 logN이 넘는 시간이 걸릴 수도 있다.
- 하지만 전체적으로 보면 모든 점은 한 번씩 들어왔다 나간다. 그래서
NlogN에 해결할 수 있다.
- 다음 점으로 이동할 때 band를 이동하고, band에 더이상 속하지 않는 점들은 tree에서 제거한다.