Closest Pair of Points

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Closest Pair of Points

n개의 point들이 2D plane에 놓여져있을 때, 두 point사이의 거리가 가장 짧은 pair를 찾는 문제이다.

1D line상에 나열되어있는 것은 $O(nlogn)$으로 자명하다.

 

가정 : x 좌표가 같은 두개의 점은 없다.

 

접근 : 

Divide : 양쪽 점의 개수가 n/2가 되도록 vertical line을 긋는다.

Conquer :  각 영역의 closest pair를 찾는다.

Combine : 각 영역의 closest pair 2개와 두 영역간의 closest pair 중 거리가 짧은 것을 반환한다.

 

 

 

 

 

 

이 알고리즘에서 Combine 하는 과정이 핵심이다. 두 영역간의 모든 조합을 찾는 것은 매우 비효율적이다. 각 영역내의 가장 짧은 거리를 $\delta$라 할때, vertical line을 기준으로 $\delta$만큼의 거리까지만 조사해도 될 것이다.

 

 

 

 

 

$2\dleta$내의 영역에서 closest path를 찾는 것을 중요한데, $1/2 \delta$씩 격자를 만든다. 한 격자안에 두개의 point가 있으면 거리가 무조건 $\delta$보다 작으므로 이 두개를 closest pair로 설정한다. 아래 그림처럼, 하나의 point에 대해 3X4 grid내에서만 path를 계산하면된다. 이 격자 밖은 path가 $\delta$를 넘어서므로, 11개의 격자에 대해서 계산을하면 된다. 그리고 이 격자를 shift하면서 검색을 진행한다. 이렇게 되면 안의 n에 대해 상수(11)만큼 검색을 진행하므로 시간은 n에 linear하다.

 

* 검색 범위를 3X4 grid대신 3X3 grid 범위로 잡아도 무관하다.

 

 

 

 

Pseudo code는 아래와 같다.

 

 

 

이 때, combine하는 과정에서 y좌표에 대해 sort하는 과정으로 인해 running time은 다음과 같다.

 

 

 

$O(nlog^2n)$ time complexity를 최종적으로 얻는다.

하지만, y좌표 sort하는 과정을 mergesort에서 했던것처럼 동일하게 진행하면 해당 부분은 $O(n)$만에 실행가능하고, running time은 다음으로 수정된다.

 

 

이를 위해서, Closest-Pair() 함수에서 $\delta$를 반환하는 것뿐만 아니라 y에 대해 sort된 list도 반환하는 것으로 수정해야한다.