선물 포장 알고리즘

선물 포장 알고리즘의 애니메이션. 빨간색 선은 이미 배치한 선이고 초록색 선은 현재 단계에서 탐색중인 배치 가능성이 있는 선이다. 또한 검은색 선은 지금까지의 탐색을 바탕으로 현재 단계에서 새로 배치할 선이다.

계산기하학에서 선물 포장 알고리즘은 주어진 점들의 집합에서 볼록 껍질을 계산하는 알고리즘이다.

평면에서의 적용

이차원의 경우, 이 알고리즘은 R. A. 자비스가 1973년에 출판한 이후 자비스 행진으로도 알려져 있다. 자비스 행진은 점의 개수 n과 볼록 껍질을 이루는 점의 개수 h에 대해 O(nh)의 시간 복잡도를 갖는다. 따라서, 볼록 껍질을 찾는 다른 알고리즘들과 비교해 보았을 때 이 알고리즘의 실제 성능은 n이 작거나 h가 n에 비해 매우 작을 것으로 예상될 때 좋은 성능을 보이게 된다. 일반적인 경우에 이 알고리즘은 다른 알고리즘보다는 저조한 성능을 발휘한다.

알고리즘

간단하게 하기 위하여, 아래의 설명은 점들이 일반적인 위치에 있다고 가정한다. 예를 들어, 그 어떠한 세개의 점도 동일 선상에 위치하지 않는다. 이 알고리즘은 간단한 수정을 통해 일직선상의 점들을 처리할 수 있는데, 극점 (볼록 껍질에 포함된 선분의 끝점들)에 대해서만 선택하는 방법과 볼록 껍질 상의 모든 점에 대해 선택하는 방법 등이 있다. 또한, 이 알고리즘의 완벽한 구현은 볼록껍질이 하나 또는 두개의 정점만을 갖는 퇴화된 경우도 처리할 수 있어야 하며, 입력 데이터와 계산 과정에서 산술 정밀도의 제한도 해결해야 한다.

선물 포장 알고리즘은 단계 i = 0 과 볼록 껍질에 포함되는 점 p₀ 에서 시작한다. 만약 pi가 가장 왼쪽에 있다면 모든 선들이 직선 p_i p₊₁의 오른쪽에 있도록 pi+1을 고를 수 있으므로 pi는 볼록껍질에 포함되는 점이 된다. 이러한 점 pi+1 을 찾기 위해 p_i 를 극좌표의 중심으로 하고 반직선 pi pi+1을 시초선으로 하여 각 점의 극 각도를 비교하는데에는 O(n)시간이 걸린다. i 에 1을 더하고 p_h = p₀ 을 만족할 때까지 h 단계를 거쳐 볼록 껍질을 구한다. 이차원에서 선물 포장 알고리즘은 점들의 집합에 실을 감는것(혹은 포장지를 감는 것)과 비슷하다.

이러한 접근은 더 높은 차원으로 확장될 수 있다.

의사

jarvis(S)
    //S는 점들의 집합
    pointOnHull= S 의 가장 왼쪽 점 // 볼록 껍질 CH(S)의 부분임이 보장된 점
    i=0
    반복
        P[i]=pointOnHull
        endpoint=S[0]// 껍질 위의 간선 후보중 초기 끝점
    for j를 1부터 |S| 까지
        if (endpoint==pointOnHull) or (S[j]의 끝점이 P[i]의 왼쪽에 있을 때)
            endpoint = S[j]//더 많이 왼쪽으로 돌게 되면 endpoint를 갱신함
    i = i + 1
    pointOnHull = endpoint
 until endpoint == P[0]//첫번째 껍질점을 포장하기

자비스의 행진은 볼록 껍질을 계산한다.

시간복잡도

안쪽 반복은 점들의 집합 S의 모든 점에 대하여 검사하고, 바깥족 반복은 껍질의 각 점에 대해 반복하므로 총 시간 복잡도는 ${\displaystyle }$다. 실행 시간은 출력의 크기에 따라 달라지기 때문에 자비스의 행진은 출력 민감 알고리즘이다.

그러나, 실행 시간이 껍질의 정점에 선형으로 의존하기 때문에, 껍질 정점의 개수 h 가 log n 보다 작을때에만 실행시간이  인 그레이엄 스캔 알고리즘보다 빠르게 작동할 수 있다. 볼록 껍질을 찾는 또 다른 알고리즘인 찬의 알고리즘은 선물 포장 알고리즘에 그레이엄 스캔의 로그 의존성을 결합하여 두 알고리즘보다 향상된 점근 실행 시간을 가진다. ${\displaystyle }$${\displaystyle }$

참조

• 볼록 껍질 알고리즘

참고 자료

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. 〈33.3: Finding the convex hull〉. 《Introduction to Algorithms》 2판. MIT Press and McGraw-Hill. 955–956쪽. ISBN 0-262-03293-7. 
• Jarvis, R. A. (1973). “On the identification of the convex hull of a finite set of points in the plane”. 《Information Processing Letters》 2: 18–21. doi:10.1016/0020-0190(73)90020-3.