[알고리즘] 10. Convex Hull

1. Convex Hull, CCW Algorithm

Convex Hull 은 평면좌표에서 어떤 점들이 있을 때 모든 점들을 포함하는 가장 작은 볼록 다각형을 의미한다. (점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형) 점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 $O(nlog n)$보다 빠를 수 없다.

앞으로 세 점의 관계를 알아낼 때 CCW (Counter Clock Wise) 알고리즘을 사용하는 경우가 많으므로 미리 알아두자. 세 점 $(x_1,y_1), (x_2,y_2), (x_3, y_3)$ 에 대해서 1 -> 2 -> 3 방향으로 이동할 때 아래 값을 이용하여 회전 방향을 판단할 수 있다.

$$x_1(y_2-y_3) + x_2(y_2-y_1)+x_3(y_1-y_2)$$

위의 값이 양수면 좌회전 (반시계), 음수면 우회전 (시계), 0이면 일직선 상의 세 점을 의미한다.

 

2. Brute-Force-ish (1) - $O(n^3)$

모든 선분모다 Convex Hull 의 일부인지를 판단하는 알고리즘이다. 선분에 포함된 두 점과 다른 모든 점들을 각각 이어봤을 때, 모두 같은 방향으로 회전하면 Convex Hull의 일부이다.

 

3. Brute-Force-ish (2) - $O(n^2logn)$

특정 점이 Convex Hull 에 포함되는 꼭짓점인지를 판단하는 알고리즘이다. 한 점에 대해서 모든 점들로 선분을 이었을 때, 선분이 존재하는 범위의 각도가 180도 이하 (외부 각도 기준으로는 180도 이상) 이면 Convex Hull 에 포함되는 점이다. 이 경우 Sorting이 필요하므로 $O(nlogn)$이 소요된다.

 

4. Package Wrapping - $O(n^2)$

Convex Hull 위에 있는 것이 보장된 점 (ex. y좌표가 가장 작은 점) 위에서 시작한다. 각 점마다 모든 점들 중 가장 왼쪽 / 오른쪽에 있는 점을 찾아서 연결하고, 그 점에서 다시 반복하여 연결하면 된다. 이 경우 최댓값을 찾는 알고리즘 처럼 Sorting 할 필요 없이 바로 비교를 시작하여 매 쌍마다 오른쪽에 있는 점을 고르면 된다. 따라서 $O(n^2)$ 만큼 시간이 걸린다.

 

5. Graham Scan - $O(nlogn)$

Convex Hull 을 찾는 가장 유명한 알고리즘이다. 기본적인 원리는 각도순으로 점을 보며 스택에 넣다가, 다음 점을 연결할 때 우회전할 경우 다시 좌회전이 되도록 지금까지 추가한 점들을 스택에서 제거하는 것이다. 알고리즘 자체는 모든 점들이 스택에 push/pop만 수행하므로 $O(1)$밖에 안걸리고, 점들을 정렬하는데는 $O(nlogn)$ 시간이 걸린다. 

(1) 2차원 평면의 점들을 정렬하고 가장 아래에 있는 점 P0를 고르고 스택에 넣습니다.(여러 개일 경우 가장 왼쪽에 있는 점)
(2) 해당 점과 나머지 점들의 기울기를 구해 x축과의 각도를 구합니다.
(3) 해당 각도를 기준으로 오름차순 정렬합니다.
(4) P0와 각도가 가장 작은 P1과 그 다음으로 작은 P2를 고릅니다. P0, P1, P2에 대해서 CCW 알고리즘을 사용하고 만약에 양수 값(반시계방향)이면 스택에 P1, P2를 넣습니다.
(5) 다음 점을 P3로 놓고, P1, P2, P3에 대해서 CCW 알고리즘을 사용합니다. 만약 0이거나 음수 값이라면 스택을 pop하고, P3를 스택에 넣어줍니다.
(6) 다음 점 P4를 놓고, P1, P3, P4에 대해서 CCW 알고리즘을 수행합니다.
- 출처: Codeground Note 

 

6. Dynamic Case - Plane Sweeping

Convex Hull 이 이미 만들어졌는데 점을 하나 추가하거나 제거하는 Dynamic Case 에서는 Plane Sweeping 을 사용한다. Closest Pair 에서 사용한 Balance Tree 수직선을 이용하여 점이 추가/제거 되는 경우를 쉽게 해결할 수 있다. - 접선을 찾아서 업데이트하는 방식

 

7. Divide and Conquer - $O(nlogn)$

Upper hull 기준으로 적용해보자. 기본적인 아이디어는 Left Hull과 Right hull 의 공통접선을 찾아서 연결하는 것이다. 공통접선을 찾는 과정에서 왼쪽은 $log n$개의 점을 탐색하고, 오른쪽에서는 점 하나당 다시 $log n$개의 점들을 탐색하므로 총 시간은 $log^2 n$ 만큼 걸리게 된다.

 

8. Farthest Point

Convex Hull 을 이용하여 Farthest Pair를 찾을 수 있는데, 교수님은 이 알고리즘을 Rotating caliper라고 알려주셨다. 이 내용에 대해서는 잘 이해를 못해서 인터넷을 찾아 봐야겠다.. - 위키피디아 설명