97. Convex Hull

$2$차원 좌표평면에 $3$개 이상의 점이 존재하고 모든 점이 한 직선 위에 있지 않을 때, 이중 몇 개의 점을 선택한 뒤 이으면 볼록다각형이 되면서 나머지 모든 점이 다각형 내부에 존재하도록 할 수 있는데, 이 볼록다각형을 볼록 껍질(Convex Hull)이라고 한다. 다음 예시를 보자.

점들의 위치가 위와 같을 때 다음과 같은 볼록 껍질을 찾을 수 있다.

점들의 좌표가 주어졌을 때 볼록 껍질을 찾아내는 것 역시 기하 문제에서 종종 접할 수 있는데, 모든 선분 쌍을 하나씩 확인하는 등의 방법은 점의 개수가 많다면 비효율적이다. 다음 두 글에서 볼록 껍질을 빠르게 찾아내는 알고리즘에 대해 살펴볼 것이다.

 

→ solved.ac tag: convex_hull