Graham's Scan(convex hull 알고리즘)

1. 개요

convex hul에 속한 모든 정점들을 찾는 알고리즘으로, $O(n\log{n})$시간의 시간 복잡도를 가진다.
효과적으로 이전 값을 탐색하고 삭제하기 위해 stack 구조를 활용하여 알고리즘이 진행된다.
3차원 공간에서는 결과를 얻을 수 없다..는 단점이 있다.
컴퓨터에서는 floating point로 각도를 계산해야 하니... 오차가 꽤나 많이 생긴다는 단점도 있다.

2. 알고리즘

1. 가장 작은 y좌표값을 갖는 정점을 시작점 $P$로 잡는다.
2. 만약 같은 y좌표를 갖는 정점이 여러개라면 x 값이 가장 작은 것을 선택한다.
3. 정점 목록을 $P$와 x축이 이루는 각도에 따라 정렬한다.
   직접 각도를 계산할 필요는 없다. x축과 이루는 각이므로, 직선의 기울기, 내적으로도 쉽게 판별이 가능하다.
4. 만약 같은 각도를 가지는 값들이 있는 경우, 더 멀리 있는 것만 선택한다. 짧은 거리에 있는 값은 삭제해도 무방하다.
   이때, 거리는 유클리드 거리가 아닌, 맨하탄 거리나 체비셰프 거리를 사용해도 관계가 없다. (계산을 단순하게 만들 수 있다.)
5. 정렬된 정점들을 따라 진행하면서, 다음 정점이 우회전 방향에 존재하는지, 좌회전 방향에 존재하는지를 판단한다.
   1. 좌회전인 경우, stack에 정점을 push 한다. 
   2. 우회전인 경우, stack을 pop 하면서 좌회전이 나올 때까지 반복한다.

위의 내용을 pseudo code로 표현하면 다음과 같다.

let points be the list of points
let stack = empty_stack()
find the lowest y-coordinate and leftmost point, called P0
sort points by polar angle with P0, if several points have the same polar angle then only keep the farthest
for point in points:
     # pop the last point from the stack if we turn clockwise to reach this point
     while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:
         pop stack
     push point to stack
end

<출처: Introduction to Algorithms>

3. 시간 복잡도

* 시간 복잡도를 좀 더 수월하게 진행하기 위해, 상수시간을 갖는 과정은 생략하였다.

 

알고리즘의 1단계에서 y값이 최소가 되는 정점을 찾는 것은 $O(n)$의 시간 복잡도를 가진다.

알고리즘의 3단계에서 정렬을 진행하는 과정은 평균적으로 $O(n\log{n})$의 시간복잡도를 가진다.

알고리즘의 5단계에서 point를 따라 순회하는 것은, 일반적으로 $O(n^2)$으로 보일 수 있으나, 각 과정에서 딱 한번씩만 사용되기 때문에, 실제로는 $O(n)$의 시간 복잡도를 갖게 된다. 
종합하면, $O(n + n + n\log{n})$의 시간 복잡도이므로 $O(n\log{n})$의 시간 복잡도를 가지게 된다.

4. 구현

** 미완**

5. 여담

x 좌표가 가장 작은 지점을 가지고도 똑같은 방식으로 진행할 수 있다. 이 경우에는 위로 올라가느냐, 아래로 내려가느냐를 기준으로 알고리즘이 동작한다.

Graham's scan 방식에서 사용된 stack은 NSV(all nearest smaller values)문제를 해결하는 알고리즘과 유사한 방식으로 동작하며, 실제로 NSV에 사용되는 병렬 알고리즘들은 Graham's scan과 같이 convex hull문제에 적용될 수 있다.