Closest pair of points(최근접쌍)

최근접쌍 문제

• 평면상에 N개의 점들이 주어질 때, 가장 가까운 두 점을 찾아라.

  Brute force 알고리즘

• Euclidean distance 이용하여 모든 두 점 쌍들 사이의 거리 구해 최솟값 발견
• Brute force 알고리즘 –> O(n*n)

분할 정복 알고리즘

1. 분할 과정
   • N개의 점들을 각각 N/2개의 점들의 부분 집합 S1, S2로 분할
   • 점들의 x좌표의 중간값을 이용해서 분할 가능
2. 정복 과정
   • 집합 S1, S2에 재귀적으로 최근접쌍 문제 푼다.
   • a1, a2는 각각 S1, S2의 최근접쌍의 거리
3. 통합 과정
   • S1의 한 점과 S2의 한 점 사이의 거리의 최솟값 a3
   • min(a1, a2, a3)가 최근접쌍 거리

• 시간 복잡도: O(n*n)
  • 통합 과정에서 S1의 한 점과 S2의 한 점의 모든 쌍들에 대해서 거리를 구해야 하므로 (n*n/4개 계산)

통합 과정 개선

• 집합 S1, S2가 수직선 L에 의해 나뉘고, a = min(a1, a2)라 하면, 수직선 L에서 x축 방향으로 거리 a안의 영역을 P로 설정
• 영역 P에서 S1과 S2에 속하는 영역을 P1, P2
  1. P1과 P2에 속하지 않는 점들은 최근접 쌍 계산에 고려할 필요 없다.
  • P1, P2에 속하지 않는 두 점 사이의 거리는 a보다 크기 때문
    

1. P1의 한 점 p에 대해 고려할 P2의 점: a X 2a 사각형 R에 속하는 점들
   • R에 속하지 않는 P2의 점은 p로부터 이미 거리가 a보다 크기 때문
     
2. P1의 한 점 p에 대해서 거리를 계산해야 할 R안의 점들은 많아야 6개
   • R에 속하는 P2의 임의의 두 점은 서로 간의 거리가 a보다 크거나 같기 때문
     
3. P2의 모든 점들을 y축에 사영해서 점들을 y좌표 값으로 정렬, P1의 한 점 p도 y축에 사영(p’)
   • 점 p’의 주변 a 안의 P2의 점들만 고려
     

• S1과 S2의 재귀 호출에서 매번 정렬을 한다면 O(N(logN)*(logN))
  • 해결법
    1. 모든 점들의 집합 S에 대해 y 좌표로 정렬한 배열 Y 생성
    2. S를 S1, S2로 분할할 때, Y 역시 S1에 속하는 점들을 y좌표로 정렬한 배열 Y1, S2에 속하는 점들을 y좌표로 정렬한 배열 Y2로 분할

  IF Y[i] is in S1
  Append Y[i] to the end of Y1
  ELSE
  Append Y[i] to the end of Y2

  • 이 분할은 O(N) 시간에 수행 가능