그레이엄 스캔
그레이엄 스캔은 평면 점 집합의 최소 볼록 다각형을 점의 각도 정렬과 스택으로 구성한다 계산 기하학·볼록 껍질 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.
| 분류 | 알고리즘 · 계산 기하학·볼록 껍질 |
|---|---|
| 주요 목적 | 평면 점 집합의 최소 볼록 다각형을 점의 각도 정렬과 스택으로 구성한다 |
| 핵심 방법 | 기준점으로부터 극각이 증가하는 순서대로 점을 정렬하고, 새 점을 넣을 때 마지막 세 점이 올바른 회전 방향을 이루지 않으면 스택에서 점을 제거한다 |
| 복잡도 | 정렬 O(n log n), 스택 스캔 O(n) |
| 적용 조건 | 동일 각도 점·중복 점과 공선 점을 포함할지 정책을 정해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
그레이엄 스캔은 평면 점 집합의 최소 볼록 다각형을 점의 각도 정렬과 스택으로 구성한다 계산 기하학·볼록 껍질 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 기준점으로부터 극각이 증가하는 순서대로 점을 정렬하고, 새 점을 넣을 때 마지막 세 점이 올바른 회전 방향을 이루지 않으면 스택에서 점을 제거한다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 정렬 O(n log n), 스택 스캔 O(n) 실제 구현에는 동일 각도 점·중복 점과 공선 점을 포함할지 정책을 정해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 컴퓨터 그래픽스와 공간 데이터 처리의 대표적인 볼록 껍질 알고리즘이다. 교차곱으로 회전 방향을 판정할 때 정수 오버플로를 고려한다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]