Thursday, January 23, 2014

Closest pair of points problem in 2D

▶ 문제
  평면에 여러 개의 점 S={p1, p2, ... , pn}이 주어졌을 때, 가장 인접해 있는 두 점을 계산하는 문제

▶ Divide & Conquer Algorithm
  (1) (Divide Step) S를 크기가 같은 2개의 집합 S1, S2로 분할한다. 분할할 경우에는 각 점을 x축의 좌표에 따라 정렬하여, 아래 그림과 같이 분할한다.
  (2) (Conquer Step) S1, S2에 대하여 재귀적으로 문제를 해결한다.
  (3) (Merge Step) S1, S2에서 가장 가까운 두 점과 S1, S2에 양 끝점이 각각 속하는 가장 인접한 두 점 중에서 가장 가까운 두 점을 계산한다.


▶ Merge Step
 {p1, p2}를 점 S1에서 가장 가까운 두 점이라 하고, δ1을 그 두 점 사이의 거리라 하자. 또한 {q1, q2}를 S2에서 가장 가까운 두 점이라 하고, δ2를 그 두 점 사이의 거리라 하자.
 δ = min{δ1, δ2}
 그리고 다음 두 조건을 만족하는 두 점 {p, q}를 찾는다.
    (1) p ∈ S1, q ∈ S2
    (2) distance(p, q) < δ
 위의 두 조건을 만족하는 점은 반드시 분할 수직선 L과의 거리가 δ 이내에 있어야한다.
P1, P2를 아래 그림과 같이, 각각 수직선 L의 양쪽에서 폭이 δ인 수직영역이라 하자.



 p ∈ S1에 대하여, S2에서 가장 가까운 점을 구하기 위해서는 위 오른쪽 그림과 같이 δ×2δ 사각형 영역에 있는 점만을 고려하면 된다.
 그러나, 이 δ×2δ 사각형 영역에는 최대 6개의 점만이 존재할 수  있다. 왜냐하면, 이 사각형 내부에 있는 점들은 최소한 δ만큼의 거리로 떨어져 있어야 하기 때문이다.
 p ∈ S1에 대하여, S2의 δ×2δ 사각형 영역에 속하는 최대 6개의 점들은 S2에 속하는 모든 점들을 y좌표에 따라서 정렬을 한 후, p의 y 좌표에 인접한 최대 6개 점과의 거리만을 계산하면 된다.


No comments:

Post a Comment