그레이엄 스캔

그레이엄 스캔 (Graham Scan) 은 계산 기하학에서 주어진 2차원 평면 상의 점들의 집합에 대한 볼록 껍질(convex hull)을 찾는 효율적인 알고리즘 중 하나입니다. 1972년에 로널드 그레이엄(Ronald Graham)에 의해 개발되었습니다.

개요

그레이엄 스캔은 주어진 점들을 정렬한 후, 스택 자료구조를 이용하여 볼록 껍질을 구성합니다. 볼록 껍질은 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형입니다. 이 알고리즘은 주로 다음과 같은 단계로 진행됩니다.

1. 기준점 선택: 주어진 점들 중 y 좌표가 가장 작은 점을 선택합니다. 만약 y 좌표가 같은 점이 여러 개 있다면, x 좌표가 가장 작은 점을 선택합니다. 이 점을 기준점 (pivot point)라고 합니다.
2. 각도 정렬: 기준점을 기준으로 나머지 점들을 반시계 방향으로 각도 순서대로 정렬합니다. 각도가 같은 점이 여러 개 있다면, 기준점으로부터 거리가 먼 점을 먼저 정렬합니다.
3. 볼록 껍질 구성: 정렬된 점들을 순서대로 스택에 추가하면서 볼록 껍질을 구성합니다. 스택에 점을 추가할 때마다 스택의 맨 위 두 점과 현재 추가하려는 점이 반시계 방향을 이루는지 확인합니다. 시계 방향을 이룬다면, 스택의 맨 위 점을 제거하고 이 과정을 반복합니다. 반시계 방향을 이루면 현재 점을 스택에 추가합니다.
4. 결과: 최종적으로 스택에 남은 점들이 볼록 껍질을 구성하는 점들입니다.

복잡도

그레이엄 스캔의 시간 복잡도는 점들을 정렬하는 단계에서 O(n log n)이고, 스택을 이용하여 볼록 껍질을 구성하는 단계에서 O(n)입니다. 따라서 전체 시간 복잡도는 O(n log n)입니다.

활용

그레이엄 스캔은 컴퓨터 그래픽스, 이미지 처리, 패턴 인식 등 다양한 분야에서 활용됩니다. 예를 들어, 충돌 감지, 최소 면적 사각형 찾기, 지도 제작 등에 사용될 수 있습니다.