그레이엄 스캔

그레이엄 스캔(Graham scan)은 평면상의 여러 점들 중에서 볼록 껍질(convex hull)을 효율적으로 구하는 알고리즘이다. 정렬 기반으로 접근하며, 가장 아래쪽 점을 기준으로 각도를 비교해 반시계 방향으로 볼록 껍질을 구성한다. 2차원 계산기하학에서 가장 널리 쓰이는 방법 중 하나다.

1 개념

• 입력: 2차원 평면상의 점 n개
• 출력: 해당 점들을 둘러싸는 볼록 껍질을 구성하는 점들의 리스트 (반시계 방향 정렬)
• 정렬 후 스택 구조를 사용해 껍질을 생성함

2 핵심 아이디어

1. 가장 아래쪽(y좌표가 가장 작음) → 가장 왼쪽(x좌표가 가장 작음)인 점 P를 기준점으로 선택
2. 나머지 점들을 P로부터의 극각(polar angle)에 따라 반시계 방향으로 정렬
3. 정렬된 점들을 차례로 처리하면서, 세 점이 시계 방향을 이루면 중간 점을 제거
4. 최종적으로 남는 점들이 볼록 껍질을 이룸

3 알고리즘 절차

1. 기준점 P₀ 선택
2. 극각 기준 정렬 (동일한 각도일 경우 거리순)
3. 스택에 첫 세 점을 삽입
4. 나머지 점들에 대해:
   1. 스택에서 최근 두 점과 현재 점으로 만든 방향 확인
   2. 시계 방향이면 스택 pop (볼록하지 않음)
   3. 반시계 방향이면 스택 push (볼록 껍질 유지)

4 ccw (Counter Clockwise) 판별 함수

• 세 점 A, B, C에 대해 방향성 판별:
  • 양수: 반시계 방향
  • 0: 일직선
  • 음수: 시계 방향
• 수식: (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x)

5 시간 복잡도

• 정렬: O(n log n)
• 스택 처리: O(n)
• 전체 시간 복잡도: O(n log n)

6 파이썬 예시

from math import atan2

def ccw(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def graham_scan(points):
    pivot = min(points, key=lambda p: (p[1], p[0]))
    sorted_pts = sorted(points, key=lambda p: (atan2(p[1]-pivot[1], p[0]-pivot[0]), p))

    hull = []
    for pt in sorted_pts:
        while len(hull) >= 2 and ccw(hull[-2], hull[-1], pt) <= 0:
            hull.pop()
        hull.append(pt)
    return hull

7 장점

• 비교적 간단하고 효율적인 구현
• 실무에서도 널리 사용되는 대표적인 볼록 껍질 알고리즘

8 단점

• 정렬이 필요하므로 매우 작은 입력(n이 작음)에서는 Jarvis March보다 느릴 수 있음

9 같이 보기

• 볼록 껍질 (알고리즘)
• 계산기하학
• Jarvis March
• Andrew's Monotone Chain
• ccw 알고리즘

10 참고 문헌

• Graham, R. L. (1972). An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters
• Cormen, T. H. et al. (2009). Introduction to Algorithms. MIT Press
• https://cp-algorithms.com/geometry/convex-hull.html