볼록 껍질 ⑤ — 가장 먼 두 점과 Rotating Calipers

1편부터 4편까지, 우리는 흩어진 점들의 볼록 껍질을 구하는 네 가지 방법을 봤다. Package Wrapping, Graham Scan, Plane Sweeping, 그리고 분할 정복. 마지막 편은 방향을 바꾼다. 껍질을 도구로 쓴다. 평면에서 가장 멀리 떨어진 두 점, 곧 점들의 지름(diameter) 을 찾는 문제인데, 모든 쌍을 재보는 $O(N^2)$ 대신 껍질을 구한 뒤 $O(N)$에 훑는 Rotating Calipers로 전체 $O(N \log N)$에 푼다.

이번에도 껍질은 1~4편에서처럼 일반 위치(한 직선 위에 점이 3개 이상 없음)를 가정하고, 이미 반시계 순서로 구해 두었다고 하자.

---

1차원에서 2차원으로

가장 먼 두 점을 찾는 문제는 1차원에선 시시하다. 수직선 위의 점들 중 가장 먼 쌍은 최솟값과 최댓값이니, 한 번 훑어 $O(N)$에 끝난다.

평면은 다르다. 어느 두 점이 가장 먼지 미리 알 수 없어, 소박하게는 모든 쌍의 거리를 재야 한다. 점이 $N$개면 쌍이 약 $N^2/2$개라 $O(N^2)$. 점이 많아지면 버겁다. 더 좋은 방법이 있을까? 볼록 껍질을 쓰면 후보를 크게 줄일 수 있다.

---

가장 먼 두 점은 껍질 꼭짓점이다

첫 관찰은 이것이다. 가장 먼 두 점은 반드시 볼록 껍질의 꼭짓점이다.

점 $q$를 하나 고정하고 함수 $f(x) = |x - q|^2$을 보자. 이 함수는 볼록이다. 그리고 볼록 함수가 볼록 다각형 위에서 갖는 최댓값은 반드시 꼭짓점에서 나온다.

이유는 이렇다. 다각형 안의 점 $x$는 꼭짓점들의 볼록 결합, 곧 $x = \sum \lambda_k v_k$ ($\lambda_k \ge 0$, $\sum \lambda_k = 1$)로 적힌다. 볼록 함수는 $f(\sum \lambda_k v_k) \le \sum \lambda_k f(v_k) \le \max_k f(v_k)$를 만족하므로, 어떤 점의 값도 꼭짓점 값의 최댓값을 넘지 못한다.

$q$를 아무 점으로 잡아도 성립하므로, 가장 먼 쌍의 한쪽을 고정하면 다른 쪽은 꼭짓점이다. 양쪽에 차례로 적용하면 둘 다 꼭짓점이다. 직관으로 말하면 내부 점은 바깥으로 밀수록 멀어지므로 후보가 되지 못한다는 뜻이다.

그래서 전략이 선다. 먼저 볼록 껍질을 구해(1~4편의 어느 방법이든 $O(N \log N)$) 후보를 껍질 꼭짓점으로 좁힌다. 남은 일은 껍질 꼭짓점들 중 가장 먼 쌍을 찾는 것이다.

---

평행선 회전과 대척점 쌍

껍질 꼭짓점만 봐도 그 쌍을 다 재면 다시 $O(H^2)$($H$는 꼭짓점 수)다. 여기서 기하적 그림 하나가 볼 쌍의 수를 확 줄인다.

볼록 다각형을 평행한 두 직선으로 양쪽에서 떠받친다고 하자(자를 양옆에 대는 느낌). 두 직선은 각각 다각형에 한 점(또는 한 변)에서 닿는다. 이렇게 마주 보며 닿는 점 쌍을 대척점 쌍(antipodal pair) 이라 부른다. 이때 두 점을 잇는 선분은 지지선과 수직일 필요가 없다.

이제 평행선의 각도를 0°에서 180°까지 돌린다. 각도가 바뀔 때마다 닿는 대척점 쌍도 바뀐다. 핵심은 이것이다. 가장 먼 두 점은 반드시 어떤 각도에서 대척점 쌍으로 나타난다. 가장 먼 쌍 $a$, $b$를 잇는 선분에 수직인 방향으로 평행선을 대면 두 직선이 정확히 $a$와 $b$에 닿기 때문이다. 그러니 모든 대척점 쌍만 훑어 그중 최대 거리를 고르면 그게 지름이다. 대척점이 아닌 쌍은 볼 필요조차 없다.

---

Rotating Calipers — $O(N)$

남은 문제는 “평행선을 연속으로 돌린다”를 어떻게 이산적인 알고리즘으로 옮기느냐다. 다행히 대척점 쌍은 각도가 돌면서 껍질 위를 한 방향으로만 이동한다. 그래서 직선을 직접 돌리는 대신, 껍질 위에 두 포인터를 두고 그것들을 회전시키면 된다. 물체를 양쪽에서 재는 자(caliper) 두 짝을 벌려 돌리는 그림이라 Rotating Calipers다.

한 걸음은 이렇다. 두 포인터가 각각 위·아래 지지선의 접점이라 하자. 각 접점에서 다음 변으로 넘어가려면 지지선을 얼마나 돌려야 하는지 비교해, 더 작은 각도로 벌어진(먼저 닿는) 쪽 포인터를 다음 꼭짓점으로 전진시킨다. 전진할 때마다 마주친 대척점 쌍의 거리를 재 최댓값을 갱신한다.

각도 비교는 삼각함수 없이 외적(cross product) 으로 한다. 외적의 크기는 한 점이 어떤 변(직선)에서 얼마나 떨어져 있는지에 비례하므로, 다음 꼭짓점이 현재 변에서 더 멀어지는 동안 포인터를 밀면 그 변의 대척점에 닿는다(1편 CCW와 같은 도구).

// hull: 볼록 껍질 꼭짓점(반시계 순서) 배열, H개. struct P·cross는 1편 정의.
// cross(O, A, B): 벡터 OA × OB (부호 있는 넓이의 2배)
// dist2(A, B): 제곱거리 — 부동소수 없이 비교하려고 제곱으로 둔다
long long best = 0;
int j = 1;
for (int i = 0; i < H; i++) {
    int ni = (i + 1) % H;                 // 변 i→ni
    // 변 i→ni에서 가장 먼 꼭짓점(대척점)까지 j를 전진
    while (cross(hull[i], hull[ni], hull[(j + 1) % H])
             > cross(hull[i], hull[ni], hull[j])) {
        j = (j + 1) % H;
    }
    // (i, j)와 (ni, j)가 대척점 쌍 후보
    best = max(best, dist2(hull[i], hull[j]));
    best = max(best, dist2(hull[ni], hull[j]));
}
// best = 지름의 제곱. 실제 지름은 sqrt(best).

---

복잡도

두 포인터는 각각 껍질을 한 바퀴만 돈다. $i$는 for 문으로 $H$번, $j$는 while 문에서 전진하되 뒤로는 가지 않아 전체를 통틀어 $H$번을 넘지 못한다. 그러니 대척점 순회는 $O(H)$이고, 껍질 크기가 최대 $N$이니 $O(N)$이다.

여기에 껍질을 구하는 $O(N \log N)$을 더하면 전체 $O(N \log N)$. 모든 쌍을 재는 $O(N^2)$과 비교하면, 껍질을 먼저 구하느라 들인 비용이 톡톡히 회수된다. 껍질은 가장 먼 점뿐 아니라 폭(width)·최소 외접 사각형 같은 여러 극값 문제의 공통 발판이 된다.

---