자비스 알고리즘

볼록 껍질을 구하는 가장 간단한 알고리즘 중 하나는 자비스 알고리즘입니다.

볼록 껍질에 반드시 포함되는 점 $p_0$ 하나를 고릅시다. 예를 들어 가장 아래에 있는 점을 고르고, 그런 점이 여러 개라면 그중 가장 왼쪽에 있는 점을 고릅니다.

이후에는 다음과 같이 진행합니다. 마지막으로 추가한 점을 기준으로 가장 「오른쪽」에 있는 점(즉, 그 점에 대한 극각이 최소인 점)을 찾아 껍질에 추가합니다. 이렇게 「닫힐」 때까지, 즉 가장 오른쪽 점이 $p_0$이 될 때까지 점을 반복적으로 추가합니다.

알고리즘의 정당성은 귀납법으로 쉽게 증명할 수 있습니다:

• 0번째 단계에서 우리는 볼록 껍질에 확실히 포함되는 점을 선택했습니다.
• $i$번째 단계에서는 나머지 모든 점이 선분 $(p_{i-1}, p_i)$의 왼쪽에 놓이도록 하는 점을 골랐으므로, 그 점들은 점 $p_i$를 확실히 가리지 않습니다.

자비스 알고리즘은 선물 포장 방법(gift wrapping)이라고도 부릅니다. 마치 포장지를 들고 집합 주위를 한 바퀴 도는 것과 같으며, 포장지는 다음 모서리마다 자연스럽게 그 주위를 감싸게 됩니다.

간단하게 하기 위해, 모든 점은 서로 다르고 정수 좌표를 가지며, 한 직선 위에 있는 세 점은 없다고 가정하겠습니다.

vector<r> jarvis(vector<r> points) {
    r p0 = points[0];
    for (r p : points)
        if (p.x < p0.x || (p.x == p0.x && p.y < p0.y))
        p0 = p;
    vector<r> hull = {p0};
    while (true) {
        r t = p0; // кандидат на следующую точку
        for (r p : points)
            // лучше никакие полярные углы не считать
            if ((p - p0) ^ (t - p0) > 0)
                t = p;
        if (t == p0)
            continue;
        else {
            p0 = t;
            hull.push_back(t);
        }
    }
    return hull;
}

볼록 껍질의 각 점(그 개수를 $h$라 합시다)마다 남은 $O(n)$개의 점 중에서 최적의 점을 찾을 것이며, 이는 전체적으로 $O(n h)$에 동작합니다.

점근 복잡도가 $O(n^2)$가 아니라 바로 $O(nh)$라는 점을 기억하는 것이 중요합니다. 볼록 껍질이 작은 문제들이 존재하며, 이런 경우에는 이 차이가 매우 중요합니다.

문제. 점들의 집합이 주어지며, 이 집합에 대해 반복적으로 볼록 껍질을 만들고 볼록 껍질에 포함된 점들을 제거합니다. 각 점에 대해 몇 번째 반복 후에 제거되는지를 구해야 합니다. 시간 복잡도는 $O(n^2)$입니다.