기하 문제에서 많이 쓰이는 볼록 껍질 알고리즘 Convex Hull에 관한 정리

벡터의 외적

Math 카테고리에 따로 정리한 글이 있다.

• 벡터의 외적

Graham Scan

무려 O(n log n) 시간에 전체 볼록 껍질에 속하는 점들을 알아낼 수 있는 알고리즘이다. 벡터의 외적 성질을 아주 잘 활용한 알고리즘

작성 중

Monotone Chain

Graham Scan의 일종의 개선 판. 처음에 각도로 정렬하지 않아도 되기 때문에 좀 더 빠르다.

작성 중

활용 예

아래와 같은 문제들을 풀 수 있다.

• 모든 점을 포함하는 최적의 다각형 구하기
• 위 다각형이 통과하는 가장 작은 지름 구하기
• 두 점 집단을 나눌 수 있는지 확인하기
• 임의의 두 점 사이의 거리의 최대값