볼록 껍질 ④ — 분할 정복과 공통 접선

1편과 2편은 점을 전부 늘어놓고 한 번에 훑었고, 3편은 점을 왼쪽부터 하나씩 더하며 껍질을 키웠다. 이번 편은 또 다른 길이다. 점들을 절반으로 갈라 각각의 껍질을 따로 구한 뒤, 두 껍질을 공통 접선(common tangent) 하나로 잇는다. 정렬에서 봤던 merge sort의 재귀 구조가 기하에서 어떻게 다시 나타나는지, 그리고 두 껍질을 잇는 접선을 얼마나 빨리 찾을 수 있는지 살펴본다.

이 포스트에서 다루는 내용

점을 절반으로 갈라 재귀로 푸는 분할 정복의 뼈대
두 껍질을 잇는 상·하 공통 접선
접선을 $O(N)$ 에 찾는 선형 워킹
접선을 $O(\log^2 N)$ 에 찾는 이진 탐색과 그 한계

이번에도 1편의 세 가정(모든 x좌표가 다르고, 모든 y좌표가 다르고, 한 직선 위에 점이 3개 이상 없다)을 그대로 쓴다. 껍질을 최좌·최우 점 기준으로 upper hull / lower hull 두 단조 사슬로 나눠 보는 3편의 어휘도 이어받는다.

나누기 — merge sort의 기하 버전

merge sort를 떠올려 보자. 배열을 반으로 갈라 각각 정렬한 뒤, 정렬된 두 조각을 하나로 합친다. 합치는 일이 $O(N)$ 이면 전체가 $O(N \log N)$ 이 된다.

볼록 껍질도 같은 틀로 풀 수 있다. 점들을 x좌표로 정렬해 두고, 가운데를 기준으로 왼쪽 절반과 오른쪽 절반으로 가른다. 각 절반의 볼록 껍질을 재귀로 구한다. 점이 두세 개로 줄면 그 점들 자체가 껍질이니 재귀가 멈춘다.

나누기 — 점을 x좌표 중앙에서 갈라 좌·우 부분 껍질을 각각 구한다. 두 껍질은 x좌표로 완전히 분리된다.

남은 일은 왼쪽 껍질과 오른쪽 껍질을 하나로 합치는 것이다. 두 껍질은 x좌표로 완전히 갈라져 있다. 즉 왼쪽 껍질의 모든 점이 오른쪽 껍질의 모든 점보다 왼쪽에 있다. 이 분리가 합치기를 깔끔하게 만든다.

재귀 구조는 merge sort와 같다. $T(N) = 2T(N/2) + (\text{합치는 비용})$ . 합치기가 $O(N)$ 이면 전체 $O(N \log N)$ 이다. 그러니 관건은 하나다. 두 껍질을 얼마나 빨리 합치느냐.

합치기의 핵심은 공통 접선

두 볼록 다각형을 하나로 감싸는 큰 껍질을 그려 보자. 새 껍질의 경계는 대부분 원래 두 껍질의 경계를 그대로 쓴다. 다만 두 군데에서 왼쪽 껍질과 오른쪽 껍질을 다리처럼 잇는 변이 새로 생긴다. 위를 잇는 다리가 상단 공통 접선(upper common tangent), 아래를 잇는 다리가 하단 공통 접선(lower common tangent) 이다.

공통 접선이란 두 껍질에 동시에 닿으면서 두 껍질을 모두 한쪽에 두는 직선이다. 상단 접선은 두 껍질을 자기 아래에 두고, 하단 접선은 자기 위에 둔다.

합치기 — 상·하 공통 접선이 두 껍질을 잇는다. 접선 바깥 사슬은 살아남고, 두 접선 사이에서 서로 마주 보는 안쪽 점들은 버려진다.

이 두 접선만 찾으면 합치기가 끝난다. 상단 접선의 두 접점을 잇고, 거기서 바깥으로 도는 사슬을 따라 내려가다 하단 접선의 두 접점에서 다시 이으면 그게 새 껍질이다. 두 접선 사이에서 서로 마주 보던 안쪽 사슬, 곧 왼쪽 껍질의 오른쪽 면과 오른쪽 껍질의 왼쪽 면은 새 경계 안에 갇혀 버려진다. 3편 Plane Sweeping에서 접선 사이 점을 버리던 것과 같은 장면이다.

그러니 합치기의 전부는 상·하 공통 접선을 찾는 일로 좁혀진다.

선형 워킹으로 공통 접선 — $O(N)$

하단 공통 접선이 무엇이었는지 다시 떠올려 보자. 두 껍질을 아래에서 떠받치는 직선, 곧 두 껍질의 모든 점이 그 위(또는 직선 위)에 놓이는 직선이다. 뒤집어 말하면, 어떤 점이 직선보다 아래로 삐져나와 있으면 그 직선은 아직 접선이 아니다. 그 점을 미처 담지 못하고 껍질 안으로 파고든 셈이기 때문이다.

그래서 방법은 이렇다. 두 껍질이 가장 가까운 곳, 즉 **왼쪽 껍질의 최우점 $a$ **와 **오른쪽 껍질의 최좌점 $b$ **를 잇는 직선에서 시작한다. 이 직선은 대개 아직 껍질을 파고든 상태다. 여기서 직선을 조금씩 아래로 눌러 내려, 삐져나온 점이 하나도 없을 때까지 만든다.

한 걸음은 1편의 CCW로 판정한다. 기준선은 언제나 지금의 두 점 $a$ , $b$ 를 지나는 직선 $ab$ 다.

오른쪽을 확인한다. $b$ 에서 사슬을 따라 한 칸 아래로 간 이웃 점을 보자. 그 이웃이 직선 $ab$ 보다 아래에 있다면, 지금 직선이 그 점을 담지 못하고 오른쪽 껍질을 파고든 것이다. 그러니 $b$ 를 그 이웃으로 옮긴다. 직선의 오른쪽 끝이 한 칸 내려가 그 점을 새로 떠받친다.
왼쪽도 똑같이 한다. $a$ 의 아래쪽 이웃이 직선 $ab$ 보다 아래에 있으면 $a$ 를 그 이웃으로 옮겨, 직선의 왼쪽 끝을 한 칸 내린다.
양쪽 다 더 내릴 이웃이 없으면, 곧 어느 껍질에도 직선 아래로 삐져나온 점이 없으면 그게 하단 공통 접선이다.

선형 워킹 — 두 껍질의 최우점·최좌점에서 시작해, 더 내려갈 수 없을 때까지 포인터를 한 칸씩 전진시켜 접선을 좁힌다.

의사코드로 쓰면 이렇다.

// L, R: 왼쪽·오른쪽 껍질(반시계 순서 배열). ccw()·struct P는 1편 정의.
// belowLine(p, q, c): 점 c가 두 점 p, q를 지나는 직선보다 아래에 있는지
//   (두 껍질은 x로 분리돼 기준선이 세로가 아니므로 '아래'가 잘 정의됨)
// nextDown(i): 하단 접선을 찾는 동안 i를 한 칸 옮길 방향의 이웃.
//   반시계 배열에서 아래쪽 사슬을 따라가는 쪽이므로,
//   왼쪽 껍질 L에서는 최우점에서 반시계(인덱스 증가) 방향,
//   오른쪽 껍질 R에서는 최좌점에서 시계(인덱스 감소) 방향이다.
//   두 포인터 모두 각자의 하단 사슬을 바깥에서 안쪽으로 한 방향으로만 돈다.
int a = rightmost(L);   // 왼쪽 껍질의 최우점
int b = leftmost(R);    // 오른쪽 껍질의 최좌점
while (true) {
    bool moved = false;
    // 두 검사 모두 지금의 직선 L[a]–R[b]를 기준으로 삼는다
    while (belowLine(L[a], R[b], R[nextDown(b)])) { b = nextDown(b); moved = true; }
    while (belowLine(L[a], R[b], L[nextDown(a)])) { a = nextDown(a); moved = true; }
    if (!moved) break;
}
// (a, b) = 하단 공통 접선. 상단 접선은 '위' 기준으로 대칭.

복잡도. 각 포인터는 껍질을 한 방향으로만 돈다. 한 번 내려간 점으로 되돌아오지 않는다. 그러니 $a$ 와 $b$ 가 전진하는 총횟수가 두 껍질의 점 수를 넘지 못하고, 접선 하나를 $O(N)$ 에 찾는다. 상·하 두 접선 모두 $O(N)$ , 접선 사이 사슬을 이어 붙이는 것도 $O(N)$ 이다. 합치기 전체가 $O(N)$ 이다.

merge와 전체 복잡도

이제 재귀를 완성한다.

hull(points):
    점이 3개 이하면 그대로 반환
    x좌표 중앙에서 좌 / 우로 분할
    Lh = hull(왼쪽 절반)
    Rh = hull(오른쪽 절반)
    return merge(Lh, Rh)   // 상·하 공통 접선으로 잇기, O(N)

merge가 $O(N)$ 이니 재귀식은 $T(N) = 2T(N/2) + O(N)$ , 풀면 $O(N \log N)$ 이다. 처음 한 번의 x좌표 정렬 $O(N \log N)$ 도 같은 차수라 전체는 $O(N \log N)$ 에 머문다. 3편이 예고한 대로, merge sort의 재귀 구조가 기하에 그대로 옮겨졌다. 배열을 합치던 자리에 두 껍질을 공통 접선으로 잇는 일이 들어갔을 뿐이다.

접선을 더 빨리 — 이진 탐색 $O(\log^2 N)$

선형 워킹은 접선 하나를 찾으려고 껍질을 훑어 $O(N)$ 을 쓴다. 더 줄일 수 있을까? 3편에서 얻은 도구가 하나 있다. 볼록 껍질의 각 사슬은 x좌표에 단조로우니, 원하는 점을 이진 탐색으로 찾을 수 있다는 것.

핵심 아이디어는 이진 탐색을 두 번 겹쳐 쓰는 것이다. 안쪽 탐색부터 보자.

안쪽: 한 점을 고정하고 반대편 접점 찾기. 왼쪽 껍질에서 점 $a$ 하나를 골라 고정한다. 그리고 $a$ 에서 오른쪽 껍질로 상단 접선을 긋는다고 하자. 외부 점에서 볼록 다각형으로는 위·아래 두 접선이 나오지만, 그중 상단 접선이 오른쪽 껍질에 닿는 점(접점)은 하나로 정해진다. 이 접점을 오른쪽 껍질을 다 훑지 않고 찾고 싶다.

오른쪽 껍질에서 후보 점을 하나 집어, 그 점이 진짜 접점보다 사슬의 앞쪽인지 뒤쪽인지만 물으면 된다. 후보 점의 양옆 변이 $a$ 에서 봤을 때 어느 쪽으로 꺾이는지를 CCW로 보면 그 답이 나온다. 사슬이 단조로우니, 답에 따라 남은 후보 구간을 절반씩 버리며 좁힐 수 있다. 그래서 접점을 $O(\log N)$ 에 찾는다. (앞·뒤를 가르는 CCW 케이스 분석은 추가 설명 글에 정리해 뒀다. 같은 도구를 여기서 다시 쓴다.)

이진 탐색 접선 — 왼쪽 껍질의 고정점에서 오른쪽 껍질의 접점을 이진 탐색으로 O(\log N)에 찾는다.

바깥: 고정한 점 $a$ 도 이진 탐색으로. 그런데 $a$ 를 아무 데나 고정하면 안 된다. $a$ 가 진짜 공통 접선의 왼쪽 접점이 아니라면, 방금 그은 접선은 왼쪽 껍질을 살짝 파고들거나 벗어난다. 그 어긋난 방향을 보면 $a$ 를 앞으로 옮길지 뒤로 옮길지 알 수 있다. 왼쪽 껍질도 단조로운 사슬이니, $a$ 의 위치 역시 이진 탐색으로 좁혀 간다.

정리하면 이렇다. 바깥 이진 탐색이 $a$ 후보를 $O(\log N)$ 번 시험하고, 그때마다 안쪽 이진 탐색이 오른쪽 접점을 $O(\log N)$ 에 찾는다. 둘을 곱하면 공통 접선 하나를 $O(\log^2 N)$ 에 얻는다는 계산이 나온다.

여기까지는 아이디어다

이 글은 위 계산을 증명하지 않는다. 두 곳이 비어 있다.

첫째, 바깥 탐색이 이진 탐색이 되려면 판정이 단조로워야 한다. 「 $a$ 를 앞으로 옮길지 뒤로 옮길지」가 사슬을 따라 한 번만 바뀌어야 절반씩 버릴 수 있다. 안쪽 탐색이 접점을 정확히 찾아 준다는 사실만으로는 이 단조성이 따라 나오지 않는다. 별도로 증명해야 하는 성질이고, 실제 알고리즘(Overmars–van Leeuwen)에서 가장 손이 많이 가는 부분이 여기다.

둘째, 뒤에서 말할 $O(\log N)$ 이어 붙이기는 분할과 합침(split·join)을 지원하는 균형 트리를 전제한다. 삽입과 삭제만 되는 트리로는 사슬 구간을 통째로 떼어 붙일 수 없다.

두 자리를 채우지 않은 채로는 $O(\log^2 N)$ 을 이 글이 세운 결과라고 말할 수 없다. 아래 서술은 그 전제 위에서 읽어 주기 바란다.

그런데 이걸로 분할 정복 전체가 빨라지지는 않는다. 접선을 $O(\log^2 N)$ 에 찾더라도, 합친 껍질을 하나의 새 배열로 만들려면 살아남는 점들을 처음부터 끝까지 $O(N)$ 에 복사해야 한다. merge가 $O(N)$ 아래로 내려오지 않으니, 전체는 여전히 $O(N \log N)$ 이다. 접선 찾기만 빨라졌을 뿐 병목은 그대로다.

그렇다면 이 빠른 접선은 언제 쓸모가 있을까? 껍질을 통째로 다시 만들지 않아도 될 때다. 3편의 동적 갱신을 떠올려 보자. 껍질을 균형 트리에 담아 두면, 접선 두 개를 찾은 뒤 그 사이를 잘라 붙이는 일을 $O(\log N)$ 에 할 수 있다. 단 이때의 트리는 삽입·삭제만 되는 것이 아니라 구간을 떼어 내고 이어 붙이는 분할·합침 연산을 지원해야 한다. 이때는 배열을 새로 만드는 $O(N)$ 비용이 없으니, 접선을 빨리 찾는 것이 곧 껍질을 빨리 고치는 것이 된다. 두 껍질을 잇는 이 접선 찾기가 바로 그 트리 기반 갱신의 핵심 부품이다.

핵심 정리

분할 정복은 점을 x좌표로 절반씩 갈라 각 껍질을 재귀로 구한 뒤 공통 접선으로 잇는다. merge sort의 기하 버전이다.
두 껍질은 상·하 공통 접선 두 개로 합쳐진다. 접선 바깥 사슬은 살아남고, 두 접선 사이의 마주 보는 안쪽 사슬은 버려진다.
선형 워킹은 두 껍질의 최우점·최좌점에서 포인터를 한 방향으로만 전진시켜 접선을 $O(N)$ 에 찾는다. merge $O(N)$ 이므로 전체 $O(N \log N)$ .
이진 탐색을 겹쳐 접선을 $O(\log^2 N)$ 에 찾는 아이디어가 있다. 다만 바깥 판정의 단조성과 분할·합침 트리라는 두 전제를 이 글은 증명하지 않는다. 게다가 껍질 배열 재구성이 $O(N)$ 이라 분할 정복 총복잡도는 그대로다. 껍질을 트리에 들고 갱신하는(3편) 상황에서 쓸모가 있다.

이어지는 글

5편에서는 껍질을 도구로 쓰는 문제로 넘어간다. 평면에서 가장 먼 두 점(지름) 을 찾는 일인데, 가장 먼 두 점은 반드시 껍질의 꼭짓점이다. 평행한 두 직선을 회전시키며 맞닿는 대척점 쌍만 훑는 Rotating Calipers로, 모든 쌍을 비교하는 $O(N^2)$ 대신 껍질을 구한 뒤 $O(N)$ 에 지름을 얻는다.

계산 기하의 다른 문제인 가장 가까운 점 쌍도 함께 보면 좋다.