평면상에서 가장 가까운 두 점(Closest Pair of Points)

출처 : https://steady-coding.tistory.com/215

 

왼쪽 평면에서 가장 가까운 두 점 사이의 거리를 dl
오른쪽 평면에서 가장 가까운 두 점 사이의 거리를 dr 이라고 하자.

그리고 두 값중 더 작은 걸 d = min{dl, dr}라고 하자.

이제 위 그림에서 S 부분을 한 변의 길이가 d/2 인 정사각형으로 쪼개보자

그러면 한 변의 길이가 d/2인 정사각형(이하 정사각형이라고 부르겠음)은 왼쪽 평면에 속하거나 오른쪽 평면에 포함된다.

하나의 정사각형 안에 두 개의 점 d1, d2가 존재한다고 가정하자. 정사각형은 하나의 평면에만 속하므로 d1, d2의 거리는 d이상이다(정사각형이 오른쪽 평면에 포함되면 d1, d2의 거리는 dr이상일 것이고, 왼쪽 평면에 포한되는 d1, d2의 거리는 dl이상일 텐데, 암튼 d보다는 크거나 같게 됨). 그런데 한 변의 길이가 d/2인 정사각형에 두 점 사이의 거리가 d 이상이라는 것은 모순이다.

따라서 각각의 정사각형 안에는 많아야 한 개의 점이 있다.

원래 관심있던것은 S에 있는 점들에 대해 (왼쪽 평면에 속하는 점)과 (오른쪽 평면에 속하는 점) 사이에 d보다 가까운 점이 있는지 여부였으나, 조건을 느슨하게 하여 S에 포함되는 점 중 d보다 가까운 점이 있는지를 알아보자.

S에 속하는 임의의 점 (x, y) 에 대해, 거리가 d보다 가까워 질 수 있는점은 [x-d, x+d] x [y-d, y+d] ∩ S 에 있는 점인데, 각 정사각형에는 많아야 한 개의 점밖에 없으므로 비교해야하는 점의 수는 상수개이다.