Convex hull Algorithm
2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)
Definition. Convex hull
The <convex hull> of a set $P$ of points in the plane is the smallest convex set containing $P$.
Equivalently, it is the largest convex polygon whose vertices are points in $P$.
-
inputs: a set $P = \{ p_1, p_2, \dots, p_n \}$ of points, where $p_i = (x_i, y_i)$
-
output: $(p_2, p_9, \dots, p_5, \dots, p_13)$, a representation of the convex hull
💥 NOTE: We assume that the points in $P$ are in general position, meaning that no three points lie on a common line.
<Convex hull Algorithm>을 살펴보기 전에 먼저 아래의 문제를 풀어보자.
For three points $p$, $q$, $r$, how do we test whether $r$ lies to the left or to the right of the directed line $\vec{pq}$?
해결 방법은 의외로 간단하다!! 그냥 $\vec{pq}$를 지나는 직선과 $\vec{pr}$을 지나는 직선의 기울기를 비교해보면 된다!!
\[\frac{q_y - p_y}{q_x - p_x} \quad \text{vs.} \quad \frac{r_y - p_y}{r_x - p_x}\]이때, 식에 나눗셈이 있는 것은 “divide by zero”의 위험이 있기 때문에, 식을 곱셈의 형태로 바꿔준다.
\[(r_x - p_x) \cdot (q_y - p_y) \quad \text{vs.} \quad (q_x - p_x) \cdot (r_y - p_y)\]만약, 점 $r$이 직선 $\vec{pq}$의 왼쪽에 있다면, 위의 그림에서도 볼 수 있듯이, $\vec{pr}$의 기울기가 $\vec{pq}$ 보다 크게 된다. 따라서,
\[\frac{q_y - p_y}{q_x - p_x} \quad < \quad \frac{r_y - p_y}{r_x - p_x}\] \[(r_x - p_x) \cdot (q_y - p_y) \quad < \quad (q_x - p_x) \cdot (r_y - p_y)\]Brute Force
어떤 두 점 $p$, $q$가 convex hull을 이룬다고 생각해보자, 그러면 $\vec{pq}$에 대해 다른 모든 점들은 $\vec{pq}$의 오른편에 존재하게 된다.
만약 이 과정을 naive 하게 진행한다면,
-
Pick two points from points set: $\displaystyle\binom{n}{2}$
-
Scan other points to determine they are in the right-side: $n$
그래서 시간 복잡도는 $O(n^3)$이 된다.
Graham’s Scan
$O(n^3)$ 수준의 알고리즘은 아직 많이 느리다. <Graham’s Scan>은 points를 정렬하고, 또 몇가지 규칙을 통해 $O(n^3)$보다 훨씬 빠른 알고리즘을 제시한다.
Algorithm.
// initialization
Sort points in $P$ by x-coord and y-coord: $O(n \log n)$
Let $p, q, r$ be the leftmost three points in the sorted list $L$.
Repeat this:
If $r$ lies to the right of $\vec{pq}$:
we move one step forward in $L$.
Otherwise:
remove $q$ from the sorted list and move one step backward in $L$ if possible.
글로 살펴보면 알고리즘의 행동이 잘 그려지지 않는다. 일단 용어를 조금 다듬으면,
- $r$는 우리가 살펴보는 직선 $\vec{pq}$의 바로 다음 정렬된 point
-
$q$는 우리의 직선 $\vec{pq}$의 끝점이다.
- “one step forward”라는 말은 $p$를 accept하고, 다음 정렬된 point로 넘어가라는 말이다.
// one step forward가 $r$을 accept 하는 것은 아니다. $r$은 언제든지 이후에 reject 될 수 있다! - “remove & one step backward”는 현재의 $\vec{pq}$에서 $q$를 reject하고, 마지막에 살펴본 2개 점으로 직선을 갱신
// 마찬가지로 이것은 $r$을 accept하는 것이 아니다!
이 과정을 반복하면, sorted list $L$에 convex hull을 이루는 점들만 남게 된다!! 😎
<Graham’s Scan>의 시간 복잡도를 분석해보자. 각 과정의 반복 횟수 별로 생각해본다면,
- rule (1)만 계속 적용 → 최대 $n-2$번 적용 가능!
- 만약 sorted list $L$에 convex hull이 아닌 점들이 있다면, 우리는 rule (2)를 통해 그런 점들을 제거하게 된다. 따라서, rule (2)는 총 $n-h$번 적용된다! ($h$ = #. of upper convex hull points)
이렇게 <Graham’s Scran>을 하게 되면, 우리는 convex hull의 위 껍질을 얻게 된다!! 나머지 아래 껍질은 sorted list의 반대에서부터 rule을 뒤집어 적용하면 얻을 수 있다!!
알고리즘 테크닉 중에는 <Convex hull trick>라는 최적화 알고리즘이 있다. 사실 이름에 “Convex hull”이 붙었지만, <Convex hull algorithm>과는 전혀 다른 종류의 알고리즘이다.
추천 문제
- 백준 1708번: 볼록 껍질 // 좋은 문제다. 자료구조들에 대한 이해와 디테일을 신경써야 했다.
- 백준 4181번: Convex Hull