Jarvis's March (자비스의 행진)

1. 개요

자비스의 행진 알고리즘은, convex hull 문제를 해결하기 위한 알고리즘이다.

말만 들으면 아이언맨에 나온 자비스가 생각난다.

Jarvis라는 사람이 만들었고 마치 행진하듯 알고리즘이 진행되어 Jarvis's March라는 이름이 붙었다.

또 다른 이름으로는 선물 포장 알고리즘이라는 이름이 있다.

 

이 알고리즘은 다른 알고리즘들에 비해 상당히 속도가 느리다는 단점이 있지만, 3차원 이상의 공간으로 확장될 수 있다는 장점이 있다.

2. 알고리즘

간단하게 진행하기 위해, 3개의 정점들이 같은 직선 위에 있는 경우는 없다고 가정한다.

1.  처음 시작할 때, 시작점 $P_0$에서 시작하고 $i = 0$으로 설정한다.
   이때, $P_0$는 Convex hull에 포함되어 있는 점 중 하나로 일반적으로 가장 왼쪽에 있는 점을 선택한다.
2. $P_i$를 극좌표의 원점으로 잡고, 반직선 $P_iP_{i+1}$를 시초선으로 하여 각 점들의 극각도를 비교한다.
   이때, 극좌표에서 $P_iP_{i+1}$이 가장 왼쪽에 있는 선이 되도록 하는 $P_{i+1}$을 설정하고, $i$에 1을 더해준다.
3. 다음으로 선택된 $P_{i+1}$이 $P_0$ 가 아닌 경우 2단계로 돌아가 과정을 반복한다.

위의 내용을 의사코드로 표현하면 다음과 같다.

algorithm jarvis(S) is
     // S is the set of points
     // P will be the set of points which form the convex hull. Final set size is i.
     pointOnHull = leftmost point in S // which is guaranteed to be part of the CH(S)
     i := 0
     repeat P[i] := pointOnHull
         endpoint := S[0] // initial endpoint for a candidate edge on the hull
         for j from 0 to |S| do
         // endpoint == pointOnHull can happen only when j == 1 and a better endpoint has not yet been setted
             if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) then
                 endpoint := S[j] // found greater left turn, update endpoint
             i := i + 1
             pointOnHull = endpoint
     until endpoint = P[0] // wrapped around to first hull point

시간 복잡도

이 알고리즘은 결과에 의존적인 알고리즘으로, h가 convex hull에 포함되는 정점의 개수일 때, 각 convex hull에 포함되는 점들에서 다른 모든 점을 탐색하므로, $O(hn)$의 시간 복잡도를 가지게 된다. 

다른 알고리즘들은 일반적인 경우에 Jarvis's March의 시간복잡도인 거의 $O(n^2)$에 가까운 값보다 더 적은 시간복잡도를 가지므로, 이 알고리즘은 다른 알고리즘들에 비해 성능이 떨어진다고 볼 수 있다.

하지만, chan's Algorithm에서 사용되어 최적의 시간 복잡도를 갖는 알고리즘에 활용되었다는 특징이 있다.

이 알고리즘은, 이전에 소개한 convex hull을 구하는 알고리즘인 Graham Scan과 동일한 또 다른 문제점을 갖고 있다.

Double Precision 때문에 정확한 결과를 얻지 못하는 경우가 꽤나 많다는 것...

그 말인 즉... 코테나 저지에서는 사용하기 어렵다는 뜻이다.

이런 문제를 방지하기 위해서는 다른 알고리즘인 Monotone Chain알고리즘을 공부하는 것이 좋겠다.