모든 쌍과 가까운 쌍
점이 n개라면 서로 다른 두 점의 조합은 n(n−1)/2개다. 각 쌍의 거리를 계산하는 방법은 간단하지만 입력이 커질수록 비교가 빠르게 늘어난다. 전체에서 최소인 한 쌍을 구하는 문제이며, 각 점마다 최근접 이웃을 따로 구하는 문제와는 출력이 다르다.
좌우로 나누기
점을 x좌표 순서로 정렬한 뒤 개수가 비슷한 두 집합으로 나눈다. 각 집합의 최소 거리를 재귀적으로 구하고, 두 결과 중 작은 값을 δ로 둔다. 남은 과제는 양쪽 집합에서 하나씩 선택한 점이 δ보다 가까운지 확인하는 것이다.
경계 부근의 후보
분할 경계에서 가로 거리가 δ보다 작은 점들만 교차 후보가 된다. 이 점들을 y좌표 순서로 살피면 평면의 거리 제약 때문에 각 점과 비교할 가까운 후보 수를 상수로 제한할 수 있다. y순서를 병합하면서 유지해야 각 단계의 결합 작업을 선형 시간에 처리할 수 있다.
입력과 구현 조건
각 단계에서 후보를 새로 정렬하는 구현은 O(n log² n)이 될 수 있으므로 분할 정복이라는 이름만으로 시간 복잡도를 판단하면 안 된다. 같은 좌표가 서로 다른 입력 점으로 두 번 나타나면 최소 거리는 0이다. 거리의 제곱을 비교할 때는 좌표 차이와 제곱이 수의 표현 범위를 넘지 않는지도 확인한다.