Closest Pair

  • Computational Geometry
  • 직관과 심하게 충돌하는 경우 많음
  • 주어진 점들 중에서 가장 가까운 쌍을 찾기 (2차원)
  • 똑같은 문제더라도 차원에 따라 문제의 난이도가 크게 차이난다.

Usually Input is given by Coordinates

보통 input은 좌표로 주어진다.

1

1 Dimensional version?

Simple sorting will solve it

2

➕ 한 가지 side story min spanning tree 문제와 max spanning tree 문제는 같은 문제이다. shortest path 문제와 longest path 문제는 다른 문제이다. 그럼 가장 가까운 두 점 찾기와 가장 먼 두 점 찾기는 같은 문제일까?

두 문제는 다른 문제처럼 보인다.
가장 가까운 두 점은 sorting을 해야 풀린다. 그래서 NlogN이 필요함
가장 멀리 떨어진 두 점은 sorting 결과 맨 앞에 있는 점과 맨 뒤에 있는 점을 찾으면 된다. 근데 이 두 점을 찾기 위해서는 sorting하지 않아도 된다! O(N)이 걸리고 가장 가까운 두 점 찾기와 다른 문제임.
2차원에서는 다르게 풀어야 한다.

Divide and Conquer

  • First, sort by X coordinates and divide, recurse

먼저 x좌표 값으로 sorting한다.

3

그리고 갯수를 반으로 나눈다.

4

그리고 왼쪽과 오른쪽에서 각각 답을 구하고, 경계선을 cross할 때도 답을 구한다.

5

After Recursions

  • We have DL and DR
  • Let D = min(DL, DR)

경계선에서 D만큼 떨어지도록 왼쪽과 오른쪽에 또 다른 경계선을 긋고 그 안에 있는 값들에 대해 고려하면 된다.

6

풀 수는 있는데 문제는 성능이다. 만약 모든 점이 경계 안에 있다면? 그럼 (N/2)*(N/2)해서 (N^2)/4가 걸려, 차라리 하나씩 비교하는게 나을 정도다.

핵심 아이디어
band 안의 임의의 점에서 반지름이 D인 원을 그려보자. 이 원 안에는 같은 밴드 내에 있는 점이 존재할 수가 없다. 만약 그러한 점이 존재한다면 D가 최솟값이 아니기 때문이다.

7

즉, 경계선을 건너서 따닥따닥 붙어있을 수는 있는데 한쪽 band에서는 따닥따닥 붙어있지 않다. 그래서 비교해야 할 대상이 많지 않다는 것을 알 수 있다.

Key Observation (Difficulty #1)

  • Comparing points within the band may take O(N^2) time
  • How many points within one square? (with side len D)

Band에서 무작정 비교하면 비교하는데만 O(N^2)의 시간이 걸린다. 시간이 너무 오래 걸리므로 다른 방법을 찾아야 한다.

밴드의 일부를 보자.

8

band 안의 한 점을 중심으로 하고 반지름이 D인 원을 그리면, 거리 D이내의 점이 없다.

9

그래서 반대쪽 band에 점이 몇 개 있는지 알아야 한다. 그리고 그 점들을 어떻게 찾을 것인지도 알아야 한다. 그림 상으로는 쉽게 찾을 수 있지만 실제로는 배열 안에 값들이 좌표로 들어있다.

우선 정사각형 하나에 점이 최대 몇 개 들어갈 수 있는지부터 생각해보자. 한쪽 변의 길이가 D인 정사각형 안에 거리가 D 이상인 점은 최대 세 개 들어갈 수 있다.

밑의 정사각형까지 고려한다면 점이 최대 다섯 개 들어갈 수 있다.

10

그래서 band 건너편의 다섯 개의 점들과만 비교하면 된다.

11

문제는 저 다섯 개의 점을 어떻게 찾느냐이다. X 좌표를 기준으로 정렬했기 때문에 Y 좌표가 크게 다를 수 있기 때문이다.

정사각형의 변의 길이가 D이기 때문에, 현재 점의 좌표를 (x1, y1)이라 하면 Y 좌표가 [y1-D, y1+D]인 점들을 반대편 band에서 찾으면 된다.

Strategy

  • Sort points within the band by Y coordinates
  • From lower to higher
  • Compare each point to the next 5 points

Band 안에 있는 점들만 따로 모아 Y좌표로 sorting한다.

12

S는 배열에서 자기 위쪽으로 5개와의 거리만 재 그 중에서 가장 작은 값을 가지고 전체 min 값을 찾는데 사용한다.

Result

GivesO(N * logN * logN) time

비교는 N번만 하지만 Y좌표 값으로 sorting을 한 번 더 해서 S(N) = 2S(N/2) + N + NlogN = O(N * logN * logN)을 얻는다.

우리가 기대한 성능을 O(NlogN)인데, NlogN을 없앨 수는 없을까?

How to make it O(NlogN)

  • Sort ALL points by y coordinate (Difficulty #2)
  • Comparison still works in O(N) (How?)
  • Sort by Y becomes Merge by Y (Why?)

13

모든 점을 다 Y 좌표에 대해 sorting하면 점이 섞여 나오기 때문에 band 안의 다섯개를 봐야 하니까 멀리까지 봐야한다. 이게 O(N)에 가능할까?

놀랍게도 여러가지 방법이 있다.

  • 방법 1: 배열을 하나 더 만들어 band 안에 있는 값들만 모은다. 그러나 이 방법은 배열을 추가로 할당하는데 시간이 걸린다.

  • 방법 2: band 안에 있는 점들이 나오면, 밴드 안의 점이 다섯 개가 나올 때까지 가서 그 안의 모든 값들에 대해 비교한다.

14

그림에서 볼 수 있듯이, 하나의 X를 보는 횟수는 5번을 넘지 않는다. 따라서 5*N의 시간이면 다 볼 수 있다.

  • 방법 3: band안에 있는 점이 나오면, 전에 본 값 중 band에 있는 값 다섯 개를 기억한다.

전체를 sorting하는 방식을 사용해도 O(N)에 비교할 수 있다.

마지막으로 sort가 merge가 되는 과정을 보자. 전체를 sorting하는 것으로 바꾸면 sorting을 하지 않고 merge하면 된다.

band 안의 값들만 Y값에 대해 sorting할 때는 왼쪽, 오른쪽으로 나눠 재귀한 후 올라올 때는 band 안에 있는 것만 Y좌표에 대해 sort되어있다.

반면 전체 배열을 Y 좌표에 대해 sorting하면 재귀가 끝나고 올라왔을 때 band 바깥의 값들도 sorting이 되어있다. –> merge sort와 같음!!

merge하는 것은 O(N)에 해결할 수 있으므로 S(N) = 2S(N/2) + N + NlogN에서 S(N) = 2S(N/2) + N + N이 되어 O(NlogN)에 해결할 수 있다!