최근접 점쌍 문제

최근접 점쌍 문제는 주어진 점 배열에서 가장 가까운 두 점을 찾는 알고리즘이다. 이 알고리즘은 문제 해결을 위해 분할 정복(Divide and Conquer) 방법론을 사용하며, O(nlogn)의 복잡도로 정확한 해를 구한다.

위 이미지에서 볼 수 있듯이, 점 배열이 주어졌을 때 가장 가까운 두 점을 찾아야 한다. 하지만 모든 점 쌍을 비교하는 O(n^2) 복잡도의 방법을 사용하지 않고 어떻게 이를 해결할 수 있을까?

이 문제를 해결하기 위한 주요 알고리즘 단계는 다음과 같다.

• X축을 기준으로 점 배열을 정렬한다. 이렇게 하면 수학적으로 자연스러운 순서로 정렬된다.

var innerPoints = mergeSort(points, sortAccording : true)

• 점 배열을 왼쪽과 오른쪽 두 부분으로 나누고, 배열에 3개 이하의 점만 남을 때까지 계속 분할한다.

• 베이스 케이스는 배열에 3개 이하의 점이 남았을 때이다. 이때는 각 점을 비교해 최소 거리와 해당 점 쌍을 반환한다.

• 아래 이미지에서 첫 번째 관찰을 할 수 있다. 두 점이 서로 매우 가까이 있지만, 알고리즘이 중간에서 분할하기 때문에 이를 감지하지 못할 수 있다.

let line:Double = (p[mid].x + p[mid+1].x)/2

• 이 문제를 해결하기 위해 Y축을 기준으로 배열을 정렬하고, 점의 X 위치와 분할선 사이의 차이를 계산한다. 이 차이가 재귀적으로 구한 최소 거리보다 작으면 해당 점을 스트립에 추가한다.

var strip = [Point]()   
var i=0, j = 0
while i<n
{
	if abs(p[i].x - line) < min
	{
		strip.append(p[i])
		j+=1
	}
	i+=1
}

• 스트립에 추가한 점들을 통해 더 작은 최소 거리를 찾을 수 있다. 아래 이미지에서 이를 확인할 수 있다.

• 스트립 내에서 점을 검색하는 과정은 브루트 포스 방식이다. 하지만 최악의 경우에도 8개 이상의 점을 반복하지 않는다는 장점이 있다.

• 그 이유는 스트립이 재귀적으로 구한 최소 거리를 변으로 하는 직사각형으로 구성되기 때문이다. Y 차이가 최소 거리보다 큰 점은 무시한다. 이러한 조건을 만족시키려면 위 이미지와 같은 형태로 점이 배치되어야 하며, 각 점은 정확히 최소 거리만큼 떨어져 있어야 한다. 이렇게 하면 각 점에 대해 4개의 가능한 점이 있고, 총 8개의 점이 된다.

while i<j
    {
        x = i+1
        while x < j
        {
            if (abs(strip[x].y - strip[i].y)) > min { break }
            if dist(strip[i], strip[x]) < temp
            {
                temp = dist(strip[i], strip[x])
                tempFirst = strip[i]
                tempSecond = strip[x]
            }
            x+=1
        }
        i+=1
    }

• 물론 항상 동일한 형태로 점이 배치되지는 않지만, 이는 최악의 경우이며 실제로는 비교할 점이 훨씬 적다. 따라서 알고리즘은 정렬 기법을 통해 성능을 향상시킨다.

• 스트립 내의 점을 비교하고 더 작은 거리를 찾으면 현재 거리를 교체한다.

이것이 최근접 점쌍 알고리즘의 작동 방식이다. 이 알고리즘은 정렬을 통해 O(nlogn)의 복잡도를 달성하며, 다양한 수학적 기법을 사용해 최적화한다.

함께 보기

알고리즘 구현을 직접 실습해 볼 수 있는 플레이그라운드를 확인해 보세요.

Wikipedia

Swift Algorithm Club을 위해 Ahmed Nader가 작성함