토픽 47 / 82

Convex Hull (볼록 껍질)

2차원 평면의 점 집합을 모두 포함하는 최소 볼록 다각형을 찾는 계산 기하학 문제로, Graham Scan, Jarvis March, QuickHull 등의 알고리즘으로 O(n log n) 시간에 해결

목적: 볼록 다각형 구성, 경계 찾기, 충돌 감지, 계산 기하 기초

특징: 볼록 다각형, 최소 경계, 반시계방향 순서, 계산 기하

응용: 충돌 감지, GIS(지리 정보), 이미지 처리, 패턴 인식, 로봇 경로

Graham Scan 알고리즘: ① 가장 낮은 y좌표 점(p0) 선택 → ② p0 기준 극각 정렬 → ③ 스택으로 반시계방향 점만 유지 → ④ O(n log n)

외적(Cross Product): 세 점의 회전 방향 판단, CCW(Counter-Clockwise) > 0(왼쪽 회전), < 0(오른쪽 회전)

Jarvis March(Gift Wrapping): 가장 왼쪽 점부터 시작 → 반시계방향으로 다음 점 선택 → O(nh), h = 껍질 점 수

QuickHull: 분할 정복, 가장 먼 점 재귀 선택, 평균 O(n log n), 최악 O(n²)

시간 복잡도: Graham Scan O(n log n), Jarvis March O(nh), QuickHull 평균 O(n log n)

공간 복잡도: O(n)

장점: 효율적(O(n log n)), 다양한 알고리즘, 계산 기하 기초

단점: 3D 복잡도 증가, 퇴화 케이스 처리 필요

적용사례: 충돌 감지(게임), GIS 경계 분석, 이미지 윤곽선, 패턴 인식

비교: Graham(정렬/빠름) vs Jarvis(출력민감/껍질작을때) vs QuickHull(분할정복/평균빠름)

연관: 계산 기하학, 외적, CCW, 극각 정렬, 충돌 감지