Closest pair of points

Closest pair of points :
2차원에 N개의 점이 있다고 있고, 이때 가장 가까운 거리의 두 점을 찾는 문제다.


먼저 가장 쉬운 방법은 모든 경우의 수에 대해서 계산을 해보는 것. 아래 처럼 되겠지.

findMinBruteforce(i, j):
min=MAX_FLOAT
for a in range(i,j):
  for b in range(i+1, j):
    cur_dist = dist(N(a), N(b))
    if (cur < min): min=cur 

이것을 더 효율적으로 할 방법은 없을까?
우선 N개의 점을 x 좌표를 기준으로 sort를 한다. 그리고 그 중간으로(N/2) 으로 왼쪽 영역과 오른쪽 영역으로 나눈다.

 왼쪽 영역의 최소거리를 dl , 오른쪽의 그것을 dr 이라고 하면 d = min(dl, dr) 이 된다. 그러면 각 영역안에서의 점들끼리는 계산이 되었지만 각 영역을 넘나드는(cross)하는 점들은 계산이 되지 않았다. 그런데 d보다 큰 것은 최소가 될 수 없으니 중간에서 d 만큼 왼쪽에 있는 영역 부터 d만큼 오른쪽에있는 영역 까지의 점들이 고려가 되어야 한다. 이 점들을 따로 뽑아서 y 좌표를 기준으로 sort해서 최소 거리를 구하면 전체 영역의 최소거리 d를 구할 수 있다.

여기서 insight는 bruteforce의 경우 모든 점들에 대해서 계산했지만, divide후에는 left/right/cross 되는 점들만 따로 생각하면 되니까그 계산횟수가 많이 줄어든다. 이것을 recursive하게 한 영역에 2~3개의 점이 있을때까지 반복하면 된다. 물론 2-3개 있을때는 bruteforce로 구현하면 되는 것이고.

나의 구현은 여기에 있다.


References:
http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
http://www.geeksforgeeks.org/closest-pair-of-points/