추가 설명 — 균형 트리에서 접선을 O(log N)에 찾기

볼록 껍질 ③에서 Plane Sweeping을 $O(N \log N)$으로 끌어내리며 “껍질을 균형 트리에 담으면 접선을 이진 탐색으로 $O(\log N)$에 찾는다”고 했다. 그때 미뤄둔 방향 판정, 즉 트리를 내려갈 때 왼쪽으로 갈지 오른쪽으로 갈지를 무엇으로 정하는지를 여기서 푼다.

---

사슬과 트리, 그리고 외부 점

3편에서 upper hull은 x좌표에 단조로운 볼록 사슬이었고, 이를 균형 BST에 x를 키로 담았다. 트리에 담긴 덕에 각 꼭짓점에서 두 가지에 바로 닿을 수 있다. 하나는 사슬 이웃, 즉 x가 바로 작은 꼭짓점(prev)과 바로 큰 꼭짓점(next)이다. 다른 하나는 트리 자식, 곧 작은 x 쪽(왼쪽 자식)과 큰 x 쪽(오른쪽 자식)이다.

외부 점 $p$는 Plane Sweeping에서 늘 가장 오른쪽에 있다. $p$에서 이 사슬에 그을 수 있는 접선은 위·아래로 두 개인데, 여기서는 위쪽 접선만 다룬다. lower hull과 아래쪽 접선은 위아래를 뒤집으면 똑같다.

전제를 두 가지 세워 둔다.

• $p$는 사슬의 모든 꼭짓점보다 x가 크다. Plane Sweeping에서 새 점이 늘 가장 오른쪽이라 저절로 성립한다. 아래에서 정할 부호 규약이 이 전제 위에 선다.
• 한 직선 위에 점이 셋 이상 있지는 않다. 1편의 가정이다. CCW가 $0$을 내는 경우가 없어져 뒤에 나올 세 갈래 판정이 서로 겹치지 않는다.

부호 규약

「위」와 「아래」를 한 번 정해 두고 끝까지 그대로 쓴다. 직선 $p$–$v$에 $p o v$라는 방향을 준다. $p$가 사슬보다 오른쪽에 있으므로 이 방향은 x가 줄어드는 쪽을 가리키고, 그때 진행 방향의 오른쪽 반평면이 화면의 위쪽이 된다.

이 글에서 「$q$가 위에 있다」는 언제나 이 뜻이다. CCW로 적으면 $\mathrm{ccw}(p, v, q) < 0$이다. 좌표로 확인해 두자. $p = (10, 0)$, $v = (0, 0)$일 때 위쪽 점 $q = (0, 1)$은 $\mathrm{ccw} = -10$, 아래쪽 점 $q = (0, -1)$은 $\mathrm{ccw} = +10$이다.

---

접점의 조건

위쪽 접선의 접점 $t$는 한마디로 직선 $p$–$t$ 아래에 사슬 전체가 들어가는 꼭짓점이다. 하지만 사슬 전체를 매번 확인하면 $O(N)$이라 이진 탐색이 되지 않는다. 다행히 볼록성 덕분에 이 조건이 국소 조건으로 바뀐다.

꼭짓점 $t$의 두 이웃(prev, next)이 모두 직선 $p$–$t$ 아래에 있으면, $t$가 접점이다.

왜 이웃 둘만 보면 충분할까? 사슬이 위로 볼록하기 때문이다. $t$의 양쪽 이웃이 직선 $p$–$t$ 아래에 있으면 그 직선은 $t$에서 사슬을 떠받치는 지지선이 되고, 위로 볼록한 사슬은 자신의 어떤 지지선도 넘지 않는다. 한 번 직선 아래로 내려간 사슬이 멀리서 다시 그 위로 솟으려면 중간 어딘가에서 위로 꺾여야 하는데, 그건 위로 볼록하다는 성질에 어긋난다. 그래서 두 이웃만 확인하면 사슬 전체를 확인한 것과 같다.

반대로 어떤 후보 $v$에서 이웃 하나가 직선 $p$–$v$ 위로 삐져나오면, 그 직선은 지지선이 아니다. 사슬의 일부가 직선보다 위에 있다는 뜻이므로 $v$는 접점이 아니다. 아래에서는 이 상황을 짧게 「뚫는다」고 부른다.

사슬의 크기가 1이면 그 꼭짓점이 곧 접점이다. 양 끝 꼭짓점은 이웃이 한쪽뿐인데, 없는 이웃은 아무 조건도 걸지 않으므로 「아래」로 친다.

---

왼쪽인가 오른쪽인가

접점이 아니라면, 어느 쪽으로 가야 접점에 가까워질까? 답은 방금 본 “뚫음”에 있다. 직선이 뚫고 들어간 쪽, 즉 이웃이 위로 삐져나온 쪽에 접점이 있다. 그래서 후보 $v$에서 볼 것은 두 이웃뿐이다. $v$의 오른쪽 이웃(next)과 왼쪽 이웃(prev)이 각각 직선 $p$–$v$의 위인지 아래인지를, 1편의 CCW로 판정한다.

• 오른쪽 이웃이 위로 삐져나옴 → 접점은 더 오른쪽(큰 x). 트리에서 오른쪽 자식으로.
• 왼쪽 이웃이 위로 삐져나옴 → 접점은 더 왼쪽(작은 x). 왼쪽 자식으로.
• 둘 다 아래 → $v$가 접점. 멈춘다.

---

왜 이진 탐색인가

후보 $v$는 트리의 한 노드다. 판정이 “오른쪽”이면 오른쪽 자식으로, “왼쪽”이면 왼쪽 자식으로 내려간다. 어느 쪽으로 가든 반대쪽 서브트리 전체가 후보에서 빠진다. 오른쪽으로 가면 x가 $v$보다 작은 꼭짓점들(왼쪽 서브트리)은 더 볼 필요가 없다. 이렇게 한쪽 서브트리를 버리며 트리 높이만큼만 내려가면 접점에 닿고, 균형 BST의 높이가 $O(\log N)$이므로 접점도 $O(\log N)$에 나온다. (균형이 이상적이면 버려지는 서브트리가 매번 남은 후보의 절반쯤 되지만, $O(\log N)$을 보장하는 건 ‘절반’이 아니라 눌러 둔 트리 높이다.)

이것이 3편에서 “이진 탐색으로 $O(\log N)$“이라고 한 말의 속이다. 사슬을 왼쪽부터 훑으면 $O(N)$이지만, 방향 판정이 매번 가지 않을 절반을 알려 주므로 트리를 타고 곧장 접점까지 내려갈 수 있다.

---

코드로

지금까지의 세 갈래 판정을 그대로 옮기면 된다.

// upper: upper hull을 x좌표 키로 담은 균형 BST
//   각 노드에서 사슬 이웃(prev: x가 바로 작은 꼭짓점, next: 바로 큰 꼭짓점)과
//   트리 자식(left: 작은 x쪽, right: 큰 x쪽)에 모두 닿을 수 있다.
// p: 외부 점(스위핑에서 가장 오른쪽), ccw(): 1편에서 정의

// q가 직선 p–v의 '위쪽(바깥)'에 있는가.
// p가 사슬보다 오른쪽이므로 p->v 방향은 x가 줄어드는 쪽이고,
// 그 진행 방향의 오른쪽 반평면이 화면의 위쪽이다. 따라서 '위'는 CCW 음수.
//   확인: p=(10,0), v=(0,0), q=(0,1) -> ccw = -10 < 0
bool above(P p, P v, P q) { return ccw(p, v, q) < 0; }

Node* upperTangent(Node* root, P p) {
    Node* v = root;
    while (true) {
        P c = v->point;
        bool rightUp = v->next && above(p, c, v->next->point);  // 오른쪽 이웃이 위
        bool leftUp  = v->prev && above(p, c, v->prev->point);  // 왼쪽 이웃이 위
        if      (rightUp) v = v->right;   // 접점은 더 오른쪽(큰 x)
        else if (leftUp)  v = v->left;    // 접점은 더 왼쪽(작은 x)
        else              return v;       // 두 이웃 다 아래 → 접점
    }
}

above의 부등호 방향은 앞의 부호 규약에서 그대로 나온 것이고, 나머지는 그림의 세 갈래를 옮긴 것이다. 아래쪽 접선은 이 부호와 자식 방향을 뒤집으면 된다.

내려갈 자식이 없어 멈추는 일은 생기지 않는다. 불변식 하나가 이를 보장한다. 시작할 때 접점 $t$는 루트의 서브트리, 곧 트리 전체에 들어 있다. 어떤 노드 $v$에서 판정이 「오른쪽」이면 $t$의 x가 $v$의 x보다 크다는 뜻인데, 트리가 x를 키로 담았으므로 $t$는 $v$의 오른쪽 서브트리 안에 있다. 그 서브트리가 비어 있지 않으니 오른쪽 자식도 있다. 왼쪽도 같다. 이 불변식이 유지되므로 루프는 반드시 $t$에서 멈춘다.

---