볼록 껍질 알고리즘
정의
볼록 껍질(convex hull)은 2차원 평면 상에 주어진 점들의 집합 $P$에 대해, 모든 점을 포함하고 그 외부에 다른 점이 존재하지 않는 가장 작은 볼록 다각형을 의미한다. 볼록 껍질 알고리즘은 이러한 다각형을 계산하는 절차를 말한다.
주요 알고리즘
| 알고리즘 | 핵심 아이디어 | 시간 복잡도 (평균) | 특징 |
|---|---|---|---|
| Graham scan | 점들을 극좌표 기준으로 정렬한 뒤, 스택을 이용해 왼쪽 회전(또는 오른쪽 회전) 여부를 판단해 껍질을 구축 | $O(n \log n)$ (정렬 단계) | 구현이 비교적 간단하고 실무에서 많이 사용 |
| Jarvis march (Gift Wrapping) | 현재 가장 바깥쪽 점에서 시작해, 가장 왼쪽(또는 오른쪽) 방향에 있는 점을 차례대로 선택 | $O(nh)$ (여기서 $h$는 껍질 점의 수) | $h$가 작을 때 효율적 |
| Quickhull | 퀵정렬의 분할 개념을 차용해, 가장 외곽의 점을 기준으로 집합을 재귀적으로 분할 | 평균 $O(n \log n)$, 최악 $O(n^2)$ | 평균적으로 빠르며 구현이 직관적 |
| Chan’s algorithm | Graham scan과 Jarvis march을 결합, 매 단계마다 제한된 크기의 부분 집합을 처리 | $O(n \log h)$ | 이론적으로 최적에 가까운 성능 |
| Kirkpatrick–Seidel (Ultimate planar convex hull) | 분할 정복 방식으로, 중간 단계에서 선분을 병합 | $O(n \log h)$ | 메모리 사용량이 비교적 적음 |
응용 분야
- 컴퓨터 그래픽스: 충돌 검사, 도형 단순화
- 지리 정보 시스템(GIS): 영역 분석, 경계 추출
- 로봇 공학: 작업 공간 정의, 경로 계획
- 데이터 분석: 이상치 탐색, 패턴 인식
- 이미지 처리: 물체 경계 검출
알고리즘 선택 시 고려 요소
- 점의 개수 $n$ 와 볼록 껍질 점의 수 $h$
- $h \ll n$이면 Jarvis march이나 Chan’s algorithm이 유리.
- 입력 데이터의 정렬 여부
- 이미 정렬된 경우 Graham scan의 $O(n)$ 단계만 수행 가능.
- 메모리 제한
- 일부 알고리즘은 추가적인 배열이나 스택을 요구함.
참고 문헌
- Preparata, F. P.; Shamos, M. I. (1985). Computational Geometry: An Introduction. Springer.
- de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer.
- O'Rourke, J. (1998). Computational Geometry in C. Cambridge University Press.
요약
볼록 껍질 알고리즘은 주어진 점 집합의 최소 볼록 다각형을 구하는 핵심적인 계산 기법으로, 다양한 분야에서 널리 활용된다. 구현 효율성은 입력 데이터의 규모와 특성에 따라 적절한 알고리즘을 선택함으로써 최적화할 수 있다.
