볼록 껍질 ③ — Plane Sweeping과 동적 갱신

1편의 Package Wrapping도, 2편의 Graham Scan도 점을 전부 미리 늘어놓고 시작했다. 하지만 점이 왼쪽부터 하나씩 도착한다면? 혹은 껍질을 다 구한 뒤에도 새 점이 계속 밀려온다면? 이번 편은 점을 x좌표 순으로 하나씩 더하며 껍질을 키우는 Plane Sweeping과, 완성된 껍질을 점이 추가될 때마다 고쳐 나가는 동적 갱신을 다룬다.

이 포스트에서 다루는 내용

껍질을 upper / lower 두 사슬로 나누는 어휘
점을 x좌표 순으로 하나씩 더하는 Plane Sweeping $O(N^2)$
껍질을 균형 이진 트리에 담아 접선을 이진 탐색하는 $O(N \log N)$
완성된 껍질을 점 추가마다 고치는 Dynamic Case

이번에도 1편의 세 가정(모든 x좌표가 다르고, 모든 y좌표가 다르고, 한 직선 위에 점이 3개 이상 없다)을 그대로 쓴다.

껍질을 반으로 나누기

평면의 볼록 껍질은 하나의 닫힌 다각형이지만, 알고리즘을 세울 때는 이를 두 개의 열린 사슬로 쪼개는 편이 편하다.

가장 왼쪽 점 $L$ 과 가장 오른쪽 점 $R$ 은 반드시 껍질 위에 있다. 1편에서 최하단 점이 껍질 위에 있던 것과 같은 이유로, 모든 점이 $L$ 의 오른쪽· $R$ 의 왼쪽에 있기 때문이다. 이 두 점이 껍질을 위아래로 가른다. $L$ 에서 $R$ 로 이어지는 위쪽 사슬을 upper hull, 아래쪽 사슬을 lower hull이라 부른다.

껍질을 반으로 나누기 — 최좌측 L과 최우측 R이 껍질을 upper hull(위)과 lower hull(아래) 두 사슬로 가른다.

이렇게 나눠 두면 각 사슬이 x좌표에 대해 단조롭다. upper hull을 왼쪽부터 따라가면 x가 계속 커지고, lower hull도 마찬가지다. 단조로운 수열에서 원하는 값을 찾는 일은 이진 탐색의 자리다. 이 성질은 뒤에서 접선을 $O(\log N)$ 에 찾을 때, 그리고 4편의 분할정복에서 두 껍질을 이을 때 결정적으로 쓰인다.

Plane Sweeping — $O(N^2)$

스위핑 라인(sweeping line) 은 세로 직선을 평면의 왼쪽 끝에서 오른쪽으로 쓸고 지나가는 상상이다. 실제 구현은 직선을 연속으로 움직이는 게 아니라, x좌표가 작은 점부터 하나씩 처리하는 이벤트 점프다. 라인이 지나온 왼쪽 영역에는 늘 “지금까지 본 점들의 볼록 껍질”을 유지한다.

점을 x좌표 순으로 정렬해 두었으니, 새로 처리하는 점 $p$ 는 언제나 지금까지 본 어떤 점보다 오른쪽에 있다. 이 사실 덕분에 $p$ 를 껍질에 더하는 일이 단순해진다. $p$ 에서 현재 껍질로 위쪽 접선과 아래쪽 접선을 하나씩 긋는다.

Plane Sweeping 한 걸음 — 새 점 p에서 현재 껍질에 위·아래 접선을 긋는다. 두 접점 사이에서 p를 마주 보는 점들은 버려진다.

두 접선이 닿는 두 접점 사이, $p$ 를 마주 보는 쪽의 껍질 점들은 이제 $p$ 와 접점들이 만든 새 경계 안쪽에 갇힌다. 이들을 버리고 그 자리에 $p$ 를 끼우면 갱신이 끝난다.

갱신된 껍질 — 접점 사이 점을 버리고 p를 끼운 결과. 버려진 점은 내부가 된다.

접선은 어떻게 찾을까? 가장 단순하게는 현재 껍질의 점을 전부 훑는다. $p$ 에서 봤을 때 가장 위(왼쪽)로 도는 점이 위쪽 접점, 가장 아래(오른쪽)로 도는 점이 아래쪽 접점이다. 방향 비교는 물론 1편의 CCW로 한다.

이 “가장 ~로 도는 점 고르기”가 한 번 훑기로 되는 데는 전제가 하나 있다. $p$ 에서 볼 때 껍질 점들이 반평면 안에 모여 있어야 한다. Plane Sweeping에서는 $p$ 가 지금까지의 어떤 점보다 x가 크므로 껍질 점이 모두 $p$ 의 왼쪽에 있고, $p$ 에서 본 방향의 폭이 $\pi$ 보다 좁다. 이 안에서는 「더 위로 돈다」가 각도의 대소와 같아져 하나의 순서가 되고, 그래서 최댓값을 한 번 훑어 고를 수 있다.

폭이 $\pi$ 를 넘으면 이 비교는 순서가 되지 못한다. $a$ 가 $b$ 보다 위로 돌고 $b$ 가 $c$ 보다 위로 도는데 $c$ 가 다시 $a$ 보다 위로 도는 일이 생기기 때문이다. 뒤의 Dynamic Case에서 새 점이 오른쪽이라는 보장이 사라지면 이 전제를 다시 세워야 한다.

// hull: 지금까지 본 점들의 껍질(반시계 순서), ccw()·struct P: 1편에서 정의
// p: 새로 도착한 가장 오른쪽 점
int up = 0, low = 0;
for (int i = 1; i < (int)hull.size(); i++) {
    if (ccw(p, hull[up],  hull[i]) > 0) up  = i;   // p에서 가장 위로 도는 접점
    if (ccw(p, hull[low], hull[i]) < 0) low = i;   // p에서 가장 아래로 도는 접점
}
// hull에서 up~low 사이(p를 마주 보는 쪽) 점들을 버리고 p를 끼운다
// hull이 반시계 순서이므로 버릴 구간은 up에서 low로 가는 쪽이고,
// 인덱스 0을 넘어 감길 수 있다

접선 두 개는 외부 점에서 볼록 다각형으로 언제나 존재하지만, 갱신 범위가 유난히 커지는 경우가 있다. 새 점 $p$ 가 지금까지의 모든 점보다 위에 있으면 $p$ 가 새로운 최상단이 되어 upper hull의 큰 구간이 한꺼번에 교체되고, 아래에 있으면 그 반대다. 이런 경계 경우도 접점 탐색에서 자연스럽게 처리된다.

복잡도. 점이 $N$ 개, 점 하나를 붙일 때 접선 찾기가 껍질 전체를 훑어 $O(N)$ 이다. 곱하면 $O(N^2)$ . 처음 한 번의 정렬 $O(N \log N)$ 은 여기에 묻힌다.

$O(N \log N)$ 으로 — 균형 BST 아이디어

$O(N^2)$ 의 낭비는 2편에서 봤던 것과 똑같다. 걸음마다 껍질 전체를 다시 훑는다. 그런데 접선을 찾는 일은 결국 “이 방향으로 가장 멀리 도는 점 고르기”이고, 앞서 봤듯 껍질의 각 사슬은 단조롭다. 단조로운 곳에서의 극값 찾기라면 이진 탐색이 통할 자리다.

그래서 각 사슬(upper hull과 lower hull)을 균형 이진 트리(balanced BST) 에 x좌표 순으로 담는다. 트리에 거는 조건은 셋이다.

키는 x좌표다. 각 사슬은 x에 단조로워 한 x 위에 점이 하나뿐이므로 키가 겹치지 않는다.
어떤 노드에서든 사슬에서 바로 앞·뒤 점을 $O(\log N)$ 안에 얻을 수 있다. 접선 사이 구간을 지울 때 이 이동이 필요하다.
삽입과 삭제 각각이 $O(\log N)$ 이다. 새 점 $p$ 의 접점을 찾을 때는 해당 사슬 트리의 루트에서 시작해, 접점이 루트보다 사슬의 앞쪽(작은 x)인지 뒤쪽(큰 x)인지 CCW로 판정하며 한쪽으로 내려간다. 트리 높이가 $O(\log N)$ 이니 접점도 $O(\log N)$ 에 나온다.

껍질을 균형 트리에 — 각 사슬을 x좌표 순으로 트리에 담으면, 새 점의 접점을 루트에서부터 방향을 정하며 O(log N)에 찾는다.

방향 판정은 다음 글에서

“접점이 사슬의 앞쪽인가 뒤쪽인가”는 후보 점의 좌우 변이 각각 어느 쪽으로 도는지 CCW로 보면 알 수 있다. 직선이 껍질을 뚫고 들어가는지 나가는지에 따라 사슬의 어느 방향으로 갈지가 갈리는데, 경우가 여럿이라 흐름을 끊는다. 이 케이스 분석은 별도의 추가 설명 글에서 따로 정리한다. 여기서는 “단조로운 사슬이라 이진 탐색이 된다”는 뼈대만 가져간다.

복잡도. 점 하나를 삽입하는 데 $O(\log N)$ . 접선 안쪽 점들을 지우는 삭제는 얼마나 들까?

여기서 구간을 통째로 지우는 특별한 연산을 쓰지는 않는다. 두 접점 사이를 앞·뒤 이동으로 한 점씩 걸어가며 지운다. 그러니 한 걸음에서 $k$ 개를 지웠다면 그 걸음의 삭제 비용은 $O(k \log N)$ 이다.

언뜻 이 $k$ 가 커 보이지만, 각 점은 평생 한 번 삽입되고 최대 한 번 삭제된다. 한 번 껍질에서 빠진 점은 내부가 되어 다시 들어오지 않기 때문이다. 그러니 모든 걸음의 $k$ 를 합쳐도 $N$ 을 넘지 못하고, 삭제에 드는 총비용은 $O(N \log N)$ 이다. 합쳐서 전체 $O(N \log N)$ .

트리를 쓰는 만큼 상수 오버헤드가 있어 실전에서는 Graham Scan보다 느릴 수 있다. 그럼에도 이 방식을 쓰는 이유는 매 걸음 ‘지금까지의 부분 껍질’이 자료구조에 그대로 남아 있다는 점이다. 그 부분 껍질이 필요한 문제에서는 이 성질이 필요하다. 바로 다음 절이 그런 경우다.

Dynamic Case — 점이 계속 추가된다면

Plane Sweeping은 점을 모두 안다고 가정하고 껍질을 한 번 만든다. 그런데 껍질을 완성한 뒤에도 점이 하나씩 새로 도착한다면 어떨까? 지도에 관측소가 늘어나거나, 실시간으로 좌표가 들어오는 상황이다.

매번 처음부터 $O(N \log N)$ 으로 다시 구하는 건 아깝다. 우리는 이미 껍질을 BST에 upper / lower 두 사슬로 들고 있으니, 그걸 고치기만 하면 된다. 새 점 $X$ 가 도착하면 먼저 물어야 할 것은 하나다. $X$ 는 지금 껍질 안인가, 밖인가?

Dynamic Case — 새 점 X가 껍질 안이면 그대로 두고, 밖이면 접선 두 개를 찾아 사이를 잘라내고 X를 끼운다.

안쪽 추가라면 껍질은 그대로다. 판정은 두 사슬로 나눈 덕에 쉽다. 먼저 $X$ 의 x좌표가 껍질의 x범위 $[L_x, R_x]$ 밖이면 $X$ 는 곧바로 외부다. 범위 안이라면 $X$ 의 x좌표 위에 놓인 변을 upper hull에서 이진 탐색으로 찾아 $X$ 가 그 변보다 아래인지 CCW로 보고, lower hull에서도 같은 것을 본다. upper hull 아래이면서 lower hull 위이면 $X$ 는 내부이고, 아무것도 할 일이 없다.

바깥쪽 추가라면 Plane Sweeping의 한 걸음과 같다. $X$ 에서 껍질로 접선 2개를 긋고, 사이 점들을 버리고 $X$ 를 끼운다. Plane Sweeping과 다른 점은 새 점이 반드시 오른쪽이라는 보장이 없다는 것뿐이다.

이 차이가 앞서 말한 전제와 맞닿는다. $X$ 가 오른쪽이 아니면 「 $X$ 에서 본 껍질이 반평면 안에 있다」가 더 이상 공짜로 오지 않으므로, 껍질 전체를 한 번 훑어 최댓값을 고르는 방식은 쓸 수 없다. 대신 $X$ 가 껍질의 x범위를 기준으로 어느 쪽에 있는지로 경우를 갈라, 각 사슬에서 이진 탐색으로 접점을 따로 찾는다. 사슬 하나만 놓고 보면 $X$ 에서 본 방향의 폭이 다시 $\pi$ 안으로 들어오기 때문이다. “단조로운 사슬에서 접점을 이진 탐색”이라는 도구는 그대로다.

결국 Dynamic Case는 새 알고리즘이 아니라, Plane Sweeping에서 만든 “껍질을 트리에 들고 접선으로 갱신한다”는 장치를 그대로 재사용하는 것이다. 껍질을 트리에 담아 둔 것이 여기서 쓰인다.

핵심 정리

껍질은 최좌·최우 점을 기준으로 upper hull / lower hull 두 단조 사슬로 나뉜다. 이 단조성이 이진 탐색을 가능하게 한다.
Plane Sweeping은 점을 x좌표 순으로 하나씩 더하며, 새 점(늘 가장 오른쪽)에서 위·아래 접선을 긋고 사이 점을 버려 껍질을 키운다. 접선을 전부 훑어 찾으면 $O(N^2)$ .
각 사슬을 균형 이진 트리에 x좌표 순으로 담으면 접선을 이진 탐색으로 $O(\log N)$ 에 찾는다. 각 점은 한 번 삽입·최대 한 번 삭제되므로 전체 $O(N \log N)$ .
Dynamic Case는 완성된 껍질에 점이 추가될 때, 안쪽이면 그대로 두고 바깥쪽이면 접선 2개로 잘라 붙인다. Plane Sweeping의 장치를 그대로 재사용한다.

이어지는 글

4편에서는 같은 $O(N \log N)$ 을 전혀 다른 길로 얻는다. 점들을 절반으로 갈라 각각의 껍질을 재귀로 구한 뒤, 두 껍질을 공통 접선(common tangent) 으로 잇는 Divide and Conquer다. 정렬에서 본 merge sort의 재귀 구조가 기하에서 어떻게 다시 나타나는지 살펴본다.

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