Closest pair of points problem

Problem : N개의 점이 주어졌을 때 가장 거리가 가까운 점 쌍을 출력하라. 거리는 유클리드 거리를 기준으로 한다.

https://www.acmicpc.net/problem/2261

Solution : 모든 쌍을 보는 문제에서 자주 쓰는 기법인 분할 정복을 사용한다.

분할 정복에 대해서 대충 안다면,

* Divide : Solve(s, e) 함수를 호출했을 때, Solve(s, m) / Solve(m+1, e) 로 두개의 집합 내에서의 모든 쌍을 본다.

* Conquer : 한쪽이 왼쪽 집합 / 한쪽이 오른쪽 집합일 때 왼쪽 집합과 오른쪽 집합간의 Closest pair를 빠르게 찾는다. 한쪽 끝이 왼쪽 / 한쪽 끝이 오른쪽이니까 뭔가 빠르게 되지 않을까. 라는 기대와 함께 (?)

와 같은 메커니즘으로 문제를 해결하는 것을 알 수 있다. 이 역시 이러한 분할 정복 패러다임으로 푸는 방법이 잘 알려져 있다.

한참 옛날에 이 알고리즘을 공부한 적이 있지만 지금 다시 생각해보니까 완전히 까먹어서, 다시 알고리즘을 복습했다. 알고리즘의 작동 원리는 다음과 같다.

 * 1. X축으로 정렬한다.

 * 2. Divide를 통해서 Solve(s, m) -> [s, m] 구간 쌍의 최소, Solve(m+1, e) -> [m+1, e] 구간 쌍의 최소를 구한다. 이러한 최소값을 Dist라고 한다.

 * 3. Conquer 과정에서, 양 집합을 다른 배열을 둬서 Y축 정렬해둔다. 이제 왼쪽 하나 오른쪽 하나 모든 쌍을 다 보는데, Y좌표 차가 Dist 미만인 점만 보는 커팅을 한다.

놀랍게도 왼쪽 쌍에 대해서 Y좌표 차가 Dist 미만인 점은 각 점에 대해서 O(1) 개이다. (최악의 경우 6개로 알고 있음) 손으로 대충 점 찍어보면 이해할 수 있을 것이다. 고로 전술한 커팅은 매우 효율적이고, 시간 복잡도는 O(Nlg^2N).

O(NlgN)으로 줄이는 방법은 X좌표 정렬된 원소를 Y좌표 정렬하는 merge sort라는 느낌으로 접근하면 된다. Solve(s, m) / Solve(m+1, e) 의 Divide 과정에서 Y축 정렬까지 되어 있다면 추가 정렬이 필요없이 O(N)에 가능할 것이다. 두 정렬된 집합을 합치는 것은 merge sort에서 많이 했던 것이고 고로 Conquer를 O(N)에 할 수 있다. 시간 복잡도 O(NlgN).

추가로, Line Sweep 테크닉으로도 O(NlgN) 시간 복잡도를 이룰 수 있다.

https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

https://www.acmicpc.net/blog/view/25