추가 설명 — 평행한 변이 만드는 동률과 대척점 쌍 열거

볼록 껍질 ⑤에서 Rotating Calipers의 뼈대를 세우며, 그 의사코드는 “일반 위치(동률 없는 경우)를 가정한 기본 뼈대”라고 못박고 평행한 변이 겹칠 때의 완전한 열거를 여기로 미뤘다. 그 미뤄둔 부분을 마저 채운다. 다만 먼저 짚을 게 있다. 뼈대가 내놓는 지름 값 자체는 평행한 변이 있어도 옳다. 이 글이 채우는 건 지름 값이 아니라 대척점 쌍을 하나의 목록으로 열거하는 별개의 문제다. 미리 밝혀 두면, 여기서 얻는 것은 빠짐없음까지다. 중복 없음은 얻지 못하고, 왜 그런지와 무엇이 더 필요한지를 마지막에 짚는다.

---

두 가지 보장을 갈라 두자

「열거한다」는 말에는 서로 다른 두 약속이 섞여 있다. 뒤에서 계속 구분해 쓸 것이므로 먼저 이름을 붙인다.

• 완전성(빠짐없음). 대척점 쌍이라면 목록에 적어도 한 번은 나온다.
• 유일성(중복 없음). 각 쌍이 목록에 많아야 한 번 나온다. 여기서 쌍은 순서를 무시한 $\{p, q\}$다.

이 글의 코드는 완전성을 만족하고 유일성은 만족하지 않는다. 같은 쌍이 순서만 바뀌어 두 번 나올 수 있다. 둘을 갈라 두지 않으면 「열거가 된다」와 「열거가 안 된다」가 같은 코드를 두고 동시에 참이 되어 이야기가 엉킨다.

---

동률은 어디서 오는가

5편에서 평행한 두 지지선을 돌리며 대척점 쌍을 훑었다. 지지선이 껍질에 닿는 방식은 보통 한 점이다. 하지만 지지선의 방향이 껍질의 어떤 변과 나란해지는 순간, 지지선은 그 변을 한 점이 아니라 통째로 떠받친다. 변의 두 끝 꼭짓점에 동시에 닿는 것이다.

이때 대척점 쌍은 하나로 딱 떨어지지 않는다. 한쪽 지지선이 변에 밀착하면 반대쪽 점 하나는 그 변의 두 끝점 모두와 대척을 이룬다. 두 지지선이 동시에 각자의 변에 밀착하면(껍질에 평행한 두 변이 있다는 뜻) 한 각도에서 대척점 쌍이 여럿 생긴다. 이 겹침이 5편이 말한 ‘동률’의 정체다. 동률은 우연이 아니라 평행한 변에서 온다. 정사각형이나 정육각형처럼 평행한 변을 가진 껍질이라면 반드시 마주친다.

---

접촉의 세 유형

지지선이 껍질에 닿는 방식을 세 가지로 나누면 동률이 선명해진다.

• 꼭짓점–꼭짓점. 두 지지선이 각각 한 꼭짓점에 닿는 일반적인 경우. 그 각도의 대척점 쌍은 하나뿐이다.
• 꼭짓점–변. 한 지지선은 한 꼭짓점에, 다른 지지선은 한 변에 밀착한다. 그 꼭짓점은 변의 두 끝점과 각각 대척을 이뤄 쌍이 둘이다.
• 변–변. 두 지지선 모두 변에 밀착한다(평행한 두 변). 한쪽 변의 두 끝점과 다른 쪽 변의 두 끝점이 서로 모두 대척이라 조합이 2×2다.

동률을 다룬다는 건 결국 뒤 두 경우, 특히 변–변에서 이 여러 쌍을 어떻게 처리하느냐의 문제다.

---

지름 값은 왜 뼈대로 이미 맞는가

결론부터 말하면, 5편 뼈대는 평행한 변이 있어도 지름을 정확히 내놓는다. 변마다 대척점을 하나만 보는 듯해도, 실제로는 두 끝점을 모두 재기 때문이다.

// 5편 뼈대의 두 줄 — 변 i→ni의 가장 먼 꼭짓점 j에 대해
best = max(best, dist2(hull[i],  hull[j]));   // (i, j)
best = max(best, dist2(hull[ni], hull[j]));   // (ni, j)

뼈대는 변 하나를 잡을 때마다 그 변에서 가장 먼 꼭짓점 하나($j$)를 찾고, 그 $j$를 변의 두 끝점 $i$, $ni$와 각각 잰다. 왜 굳이 두 번 잴까? 직사각형 하나로 보면 바로 드러난다.

꼭짓점이 $A(0,0)$, $B(4,0)$, $C(4,1)$, $D(0,1)$인 직사각형을 생각하자. 지름은 대각선 $AC$로 길이가 $\sqrt{17}$이다. 뼈대가 아래 변 $A \to B$를 처리할 차례라고 하자. 이 변에서 가장 먼 꼭짓점은 위쪽의 $C$와 $D$(둘 다 높이 1)이고, 포인터 $j$는 그중 하나, 예컨대 $C$에 멈춘다. 이제 $j = C$를 두 끝점과 각각 재면 이렇다.

• $\text{dist}(A, C) = \sqrt{17}$, 곧 지름이다.
• $\text{dist}(B, C) = 1$, 짧은 변이다.

아래 변 하나를 처리한 것만으로 지름이 잡혔다. 그런데 만약 $j$가 $C$가 아니라 $D$에 멈췄다면? 그때는 $\text{dist}(A, D) = 1$, $\text{dist}(B, D) = \sqrt{17}$라 이번엔 반대로 $B$ 쪽이 지름의 끝이 된다. 지름의 한쪽 끝은 늘 “가장 먼 꼭짓점 $j$“로 잡히지만, 다른 쪽 끝이 그 변의 $i$인지 $ni$인지는 미리 알 수 없다. 그래서 $j$를 두 끝점 모두와 재두면, 어느 쪽이 지름의 끝이든 놓치지 않는다.

이건 직사각형만의 우연이 아니다. 지름을 이루는 쌍 $(u, v)$를 양쪽에서 평행 지지선으로 누른 채 천천히 돌려 보자. 꼭짓점을 누르는 지지선은 그 꼭짓점에서 만나는 두 변 사이 각도만큼만 기울 수 있어서, 계속 돌리면 한쪽 지지선이 어느 변 전체에 닿는 순간이 온다. 그 변을 $i \to ni$라 하면, 맞은편 평행선이 닿는 점 $v$는 그 변에서 가장 먼 꼭짓점 $j$이고, $u$는 그 변의 두 끝점 중 하나($i$ 아니면 $ni$)다. 지름은 언제나 어떤 변의 끝점과 그 변에서 가장 먼 꼭짓점의 쌍으로 나타나고, 뼈대는 모든 변에서 그 조합을 두 끝점 다 재므로 반드시 만난다.

변–변 동률에서 생기는 ‘교차’ 쌍(한 변의 끝점과 맞은편 변의 반대쪽 끝점)도 안전하다. 한 변에서 놓치더라도 맞은편 변을 처리할 때 그 쌍이 다시 후보로 올라오기 때문이다. 직사각형이 그렇다. 대각선은 $AC$와 $BD$ 둘인데, $AC$는 아래 변에서, $BD$는 오른쪽 변 $B \to C$에서 잡힌다. 지름은 최댓값만 필요하니, 평행한 변이 있어도 뼈대만으로 안전하다.

---

빠짐없는 열거는 왜 다른 문제인가

그렇다면 5편은 왜 뼈대를 “일반 위치 기본 뼈대”로 좁혔을까? 지름 값이 아니라 대척점 쌍을 목록으로 뽑는 문제가 남기 때문이다. 폭(width), 최소 외접 사각형, 두 볼록 다각형 사이 거리 같은 문제는 지름 하나가 아니라 대척점 쌍 하나하나를 손에 쥐어야 풀린다. 여기서 평행한 변의 동률이 정확히 문제를 만든다.

변–변 동률을 다시 보자. 뼈대가 변 $i \to ni$를 처리할 때 포인터 $j$는 맞은편 변의 한 끝(그림의 $j$)에 멈춘다. strict > 비교라 다음 꼭짓점 $j{+}1$로는 넘어가지 않는다. 두 외적(넓이)이 같아 >가 거짓이기 때문이다. 그래서 뼈대가 이 변에서 기록하는 대척점 쌍은 $(i, j)$와 $(ni, j)$뿐이고, 맞은편 변의 다른 끝 $j{+}1$과 이루는 교차 쌍은 빠진다.

이 각도에서 대척을 이루는 쌍은 넷이다. 가까운 쪽 지지선이 변 $i \to ni$ 전체에 닿고 맞은편이 $j$, $j{+}1$에 닿으므로 $\{i, ni\} \times \{j, j{+}1\}$이 모두 대척점 쌍이다. 아래 코드는 이 변에서 그중 둘만 적는다.

• $(i, j)$ — 이 변에서 적는다.
• $(i, j{+}1)$ — 동률 분기가 있어야 적는다. 뼈대만으로는 건너뛴다.
• $(ni, j)$, $(ni, j{+}1)$ — 이 변에서는 적지 않는다. 루프가 맞은편 변에 이르렀을 때 순서가 뒤집힌 꼴로 나온다.

지름 값을 구할 때 쓰던 두 줄 dist2(hull[i], hull[j])와 dist2(hull[ni], hull[j])는 거리를 두 번 재는 것이지 쌍을 두 개 적는 것이 아니다. 값만 필요할 때와 목록이 필요할 때가 갈리는 자리가 여기다.

지름만 볼 때는 $(i, j{+}1)$을 놓쳐도 그 거리가 다른 변에서 다시 잡혔지만, 모든 쌍을 하나씩 필요로 하는 문제에서는 이 하나가 통째로 사라진다. 그게 5편이 미룬 ‘완전한 열거’의 공백이다.

---

코드

동률 분기를 뼈대에 얹으면 이렇다. 5편 뼈대에서 달라진 곳은 report와 그 아래 if 하나뿐이다.

// hull: 반시계 볼록 껍질, H개. cross는 1편 정의.
// report(a, b): 대척점 쌍 (hull[a], hull[b])을 목록에 추가
int j = 1;
for (int i = 0; i < H; i++) {
    int ni = (i + 1) % H;
    // 변 i→ni에서 가장 먼 꼭짓점까지 j를 전진 (strict '>' 유지)
    while (cross(hull[i], hull[ni], hull[(j + 1) % H])
             > cross(hull[i], hull[ni], hull[j])) {
        j = (j + 1) % H;
    }
    report(i, j);                              // (i, j)는 대척점 쌍

    // 변 i→ni 가 변 j→(j+1) 과 평행하면(넓이 동률) 이 각도에 쌍이 여럿
    if (cross(hull[i], hull[ni], hull[(j + 1) % H])
          == cross(hull[i], hull[ni], hull[j])) {
        report(i, (j + 1) % H);                // 교차 대척점 쌍 하나 더
    }
}

• 지름만 필요하면 이 if 분기는 없어도 된다. 놓친 교차 쌍은 맞은편 변에서 다시 후보로 오르기 때문이다. 분기가 필요한 건 대척점 쌍을 목록으로 뽑을 때뿐이다.
• 완전성은 만족한다. 대척점 쌍이라면 어느 변에서든 한 번은 나온다. 이 변에서 적지 않은 $(ni, \cdot)$ 쌍은 루프가 맞은편 변에 이르렀을 때 순서가 뒤집힌 꼴로 나온다.
• 유일성은 만족하지 않는다. 같은 쌍이 순서만 바뀌어 두 번 나온다. 직사각형이 그렇다. 아래 변이 $(A, C)$를 적으면 위 변에서 $(C, A)$가 또 나온다. report 호출은 8번인데 무순서 쌍으로 세면 6개다.
• 쓰려면 정규화해서 걸러야 한다. 각 쌍을 $(\min, \max)$로 정규화해 집합에 넣으면 유일성이 회복된다. 껍질 크기 $H$에 대해 대척점 쌍은 $O(H)$개이므로 이 후처리는 전체 복잡도를 바꾸지 않는다.
• 후처리 없이 한 번씩 내려면 종료를 따로 관리해야 한다. Toussaint의 고전적 열거법은 첫 대척점의 위치를 시작 마커로 기억해 두고, 포인터가 껍질을 한 바퀴 돌아 그 마커에 이르면 멈춘다. 맞은편 변에서 같은 쌍을 두 번째로 훑기 전에 끊는 것이다. 그 순회·종료 규칙을 그대로 옮기는 건 이 글의 범위를 넘는다.

---