[Algorithm] 최근접 점의 쌍 알고리즘 (Closest Pair)

💡최근접 점의 쌍 (Closest Pair) 문제?

• 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제

 

💡간단한 해결 방법 : O(n^2) 알고리즘

• 모든 점에 대해 각각의 두점 사이의 거리를 계산하여 가장 가까운 점의 쌍 찾기
• 비교헤야 할 쌍은 몇개?
  • nC2 = n(n-1)/2 = O(n^2)
• 한쌍의 거리 계산은 O(1)
• 따라서 시간 복잡도는 O(n^2)

 

💡보다 효율적인 해결방법 : 분할 정복 이용

1. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍 찾기
2. 2개의 부분해 중에서 짧은 거리 (d)를 가진 점의 쌍을 일단 찾기 (재귀적으로)
3. 결합 : 두개의 부분해를 취합할 때는 반드시 두 부분 문제서 각각 한 점 씩 포함되는 점의 쌍 중에서 그 거리가 d보다 작은 쌍 찾기 (중간 영역 고려)
4. 만약 d보다 작은 쌍이 나왔다면, 그런 쌍 중에 가장 짧은 쌍이 해이다. 그렇지 않다면 거리가 d인 쌍이 해이다.

 

중간 영역에 있는 쌍들을 검색하는 방법

• 점들의 집합을 S라고 하고, S를 둘로 나눈 집합을 SL, SR 이라고 하자
• SL, SR에서 각각 찾은 closest pair을 각각 CPL, CPR 이라고 하고, 두점 사이의 거리를 dist()함수로 표시하면
  • d = min(dist(CPL), dist(CPR)) = min{10, 15} = 10
• 그러면, 분할한 지점에서 X축으로 +-d (+-10) 인 범위에 속한 점들만 검색해도 충분
• x좌표의 오름차순으로 점들이 정렬되어 있다면, 중간영역 과정에서 검색할 점들을 탐색할 수 있다.

---

💡 최근접 점의 쌍 분할 정복 알고리즘

1. if (i<=3) return (2개 또는 3개의 점 사이의 최근접 쌍)
2. 정렬된 S를 같은 크기의 SL과 SR로 분할
   1. |S|가 홀수이면, |SL| = |SR| + 1 이 되도록 분할
3. CPL = ClosestPair(SL) //CPL = SL에서의 최근접 점의 쌍
4. CPR = ClosestPair(SR) //CPR = SR에서의 최근접 점의 쌍
5. d = min{dist(CPL), dist(CPR)} 일때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾아서 이를 CPC라고 하자.
6. return (CPL, CPR, CPC 중에 가장 거리가 짧은 쌍)

 

예제 알고리즘

위의 사진에 있는 모든 점들의 쌍중 가장 최근접 점의 쌍을 찾아보자

 

 

❗️ 중간영역에서 CPC을 찾을 때, SL과 SR이  모두 중간영역에 있을 경우? O(n^2)

• Brute force한 방법으로 closest pair를 구한다면 O(n^2) -> 아무런 이득을 볼 수 없음

• for(i=1;i<=n;i++){
  	for(j=i+1;j<=n;j++){
      	d(ij) = dist(pi,pj)를 구하고, d(ij)<d 이면, d=d(ij)
          }
  }​

• 중간 영역에 있는 점들을 y좌표를 기준으로 오름차순 또는 내림차순으로 정렬하자
• -> y 축으로 내림차순으로 정렬한 점들을 p1, p2, ... pn이라고하자.
• 점 pi의 y좌표를 yi 라고하자. 점들이 y 방향으로 정렬되어 있으므로, 아래와 같은 방법이 보다 효율적이다.

  • for(i=1;i<=n-1;i++)
    	for(j=1+1;j<=n;j++)
        	if(yi-yj>=d) break;
            d(ij) = dist(pi, pj)를 구하고, d(ij)<d 이면 d=d(ij)

    그러나, 위 과정은 d 값에 따라 그 속도가 결정된다.

 

💡실행코드 C++

#include <iostream>
#include <vector> // 벡터 리스트시 사용
#include <utility> // 입력값 -> 벡터리스트 한쌍으로
#include <cmath> // sqrt 사용
#include <sstream> // 입력값 추출 시 사용

#define X first
#define Y second

// 입출력 속도 개선
#define IOFAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
vector<pair<long long, long long> > list;

// 입력 추출 및 문자열 -> 숫자 변경 함수
void parseInt(string tmp) {
    stringstream ss(tmp);
    vector<long long> temp;
    for (int i; ss >> i;) {
        temp.push_back(i);
        if (ss.peek() == ',' || ss.peek() == ' ')
            ss.ignore();
    }
    list.push_back(make_pair(temp[0], temp[1]));
}

void quickSortX(int start, int end){
    if(start >= end) return;
    int key = start;
    int i = start + 1, j = end;
    pair<long long, long long> temp;

    while (i<=j){
        while(i<=end && list[i].X <= list[key].X) i++;
        while(j>start && list[j].X >= list[key].X) j--;
        if(i>j){
            temp = list[j];
            list[j] = list[key];
            list[key] = temp;
        } else {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
    }
    quickSortX(start, j-1);
    quickSortX(j+1, end);
}

void quickSortY(int start, int end){
    if(start >= end) return;
    int key = start;
    int i = start + 1, j = end;
    pair<long long, long long> temp;

    while (i<=j){
        while(i<=end && list[i].Y <= list[key].Y) i++;
        while(j>start && list[j].Y >= list[key].Y) j--;
        if(i>j){
            temp = list[j];
            list[j] = list[key];
            list[key] = temp;
        } else {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
    }
    quickSortY(start, j-1);
    quickSortY(j+1, end);
}

double Dist(pair<long long, long long> x, pair<long long, long long> y){
    return sqrt((x.X-y.X) * (x.X-y.X) + (x.Y-y.Y) * (x.Y-y.Y));
}

double CPCCheck(int left, int right, double d){
    quickSortY(left, right);
    for(int i=left; i<=right; ++i){
        for(int j=i+1; j<=right; ++j){
            if(list[j].Y-list[i].Y>d) break;
            double tmp = Dist(list[i], list[j]);
            d = d < tmp ? d : tmp;
        }
    }
    return d;
}

double ClosestPair(int left, int right){
    int dots = right-left+1;
    double min;

    if(dots == 2){ // 점이 두점일땐 그냥 구하면 됨
        return Dist(list[left], list[right]);
    } else if(dots == 3){ // 3점일때 3점사이 거리
        double a = Dist(list[left], list[left + 1]);
        double b = Dist(list[left + 1], list[left + 2]);
        double c = Dist(list[left+2],list[left]);
        if(a<b){
            if(a<c){
                return a;
                }
                return c;
                }
        else{
            if(b<c){
                return b;
            }
            return c;
        }
    } else {
        int mid = (left + right) / 2;
        double a = ClosestPair(left, mid);
        double b = ClosestPair(mid+1, right);
        min = a < b ? a : b;
        return CPCCheck(left, right, min);
    }
}

int main() {
    IOFAST;
    int dots;
    cin >> dots;
    cin.ignore();
    for(int i=0; i<dots; ++i){
        string s;
        // 줄 바꿈 까지 입력 받기
        getline(cin, s);
        parseInt(s);
    }
    quickSortX(0, list.size());

    // for 소수점 6자리 출력
    cout << fixed;
    cout.precision(6);

    cout << ClosestPair(0, list.size());
}

 

---

💡시간 복잡도

입력 s에 n개의 점이 있다면,

• 전처리 과정으로서 s의 점을 x-좌표로 정렬 : O(nlogn)
• s에 3개의 점이 있는 경우에 3번의 거리 계산이 필요하고, s의 점의 수가 2이면 1번의 거리 계산이 필요하므로 O(1)의 시간
• 정렬된 s를 sl과 sr로 분할 하는데, 이미 배열에 정렬되어 있으므로, 배열의 중간 인덱스로 분할 : O(1)의 시간
• sl과 sr에 대하여 각각 ClosestPair을 호출하는데, 분할하며 호출되는 과정은 합병정렬과 동일
• (1) d = min{dist(cpl), dist(cpr)}일 때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾는다.
  • y 좌표로 정렬하는 시간 : O(nlogn)
  • 그다음 아래에서 위로 올라가며 각 점에서 주변의 점들 사이의 거리를 계산하는데 O(1)의 시간
    • 각 점과 거리를 계산해야하는 주변 점들의 수는 O(1)개 이기 때문!
• (2) cpl, cpc, cpr 점의 쌍중에 가장 짧은 거리를 가진 점의 쌍을 리턴 :  O(1)의 시간
• k층까지 분할 된 후, 층별로 (1), (2) 이 수행되는 combine (취합) 과정을 진행하므로
  • ClosestPair 알고리즘의 시간복잡도 = O(nlog(^2)n)
    • 각층의 y좌표 정렬의 수행시간은 O(nlogn)
    • 여기에 층 수인 logn

➕ O(nlogn)알고리즘으로 개선하기

• 입력의 점들을 y 좌표를 기준으로 전처리 과정에서 미리 정렬하기

• double ClosestPair(int left, int right){
      int dots = right-left+1;
      double min;
  
      if(dots == 2){
          return distance(list[left], list[right]);
      } else if(dots == 3){
          double a = distance(list[left], list[left + 1]);
          double b = distance(list[left + 1], list[left + 2]);
          return a < b ? a : b;
      } else {
          int mid = (left + right) / 2;
          double a = ClosestPair(left, mid);
          double b = ClosestPair(mid+1, right);
          min = a < b ? a : b;
          return CheckBand(left, right, min);
      }
  }

• 이 코드에서 if, else if문에는 정렬을 그냥 넣어줌 -> 2, 3 개니까 그냥 O(1)으로 정렬
• else 문에는 mergesort를 넣어줌 -> 이미 정렬된 2개, 3개 짜리 -> O(n)

💡응용

• 컴퓨터 그래픽스
• 컴퓨터 비전
• 지리정보 시스템
• 분자 모델링
• 항공 트래픽 조정
• 마케팅 (주유소, 프랜차이즈 신규 가맹점 등의 위치 선정 등)

 

---

 

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업