볼록껍질

볼록껍질(Convex Hull)은 컨벡스 헐이라고도 불리며 주어진 점들을 모두 포함하는 최소 크기의 다각형을 말합니다.

볼록껍질을 구하기 위하여 그라함 스캔 알고리즘(Graham's Scan Algorithm)을 사용합니다.

이 알고리즘은 먼저 y좌표가 가장 작고 y좌표가 같다면 x좌표가 가장 작은 점을 선택한 뒤,

그 선택한 점을 제외한 점을 반시계 방향으로 정렬하여 순서대로 점을 보며 스택에 push 합니다.

이 때 push하기 전 스택에 점이 2개 이상 들어있을 때 그 두 점을 이은 직선 기준으로 왼쪽에 이 점이 있지 않다면

스택에서 조건에 만족할 때까지 pop한 뒤 push를 해주며

모든 점을 보았을 때 스택에 남아있는 점이 최소 크기의 다각형을 이루는 점입니다.

직선 기준으로 왼쪽에 있는 지는 앞서 계산 기하에서 배운 CCW를 이용하여 확인해볼 수 있으며

이 알고리즘의 시간복잡도는 N-1개의 점을 정렬하는 데에 걸리는 시간이 시간복잡도를 지배하기에 O(NlgN)입니다.

볼록껍질을 구한 뒤 이 볼록다각형을 이용한 추가적인 응용 또한 많이 이루어지는 중요한 기하 알고리즘입니다.

기본 문제

1708번: 볼록 껍질

2254번: 감옥 건설

3878번: 점 분리