ㅇ







4번째 단계를 해결할 때 가능한 모든 쌍들을 탐색 해 본다면, 역시 제곱에 비례하는 시간이 필요할 것이다. 하지만 점들이 분포되어있는 특별한 성질을 이용한다면, 선형적 시간안에 해결될 수 있다. 3번 단계를 통해서, 가장 가까운 두 점은 d=min(dLmin,dRmin){\displaystyle d=min(d_{Lmin},d_{Rmin})}보다 더 멀리 떨어져 있을 수는 없음을 알 수 있다. 따라서 분할선 왼쪽에 있는 각각의 점 p{\displaystyle p}에 대해서, p{\displaystyle p}의 y{\displaystyle y}좌표를 중심으로 하고 분할선 오른쪽에 존재하는 (d,2d){\displaystyle (d,2d)} 크기의 직사각형 내부에 존재하는 점들에 대해서만 거리를 계산해도 된다.

이 직사각형은 최대 6개까지의 점만을 포함하기 때문에, 최대 6 n {\displaystyle 6n} 쌍의 점들에 대해서만 계산을 해도 충분히 최소 거리를 구할 수 있다.

이 알고리즘의 연산의 수행 횟수를 재귀식을 표현하면 T(n)=2T(n/2)+O(n){\displaystyle T(n)=2T(n/2)+O(n)}으로 표현할 수 있으며, 마스터 정리에 따라 O(nlogn){\displaystyle O(nlogn)}로 나타낼 수 있다.





빨간 글씨가 이해가 안됩니다.


직사각형에서의 6개의 점만 계산을 한다는 것은 점들이 같은 간격으로 규칙적 분포가 되어있을 때만 가능한 거 아닌가요?


애초 점들은 무작위로 분포되어 있는데...