convex hull (3) 썸네일형 리스트형 99. Andrew's Algorithm 앤드류 알고리즘(Andrew's Algorithm)은 점 $n$개의 볼록 껍질을 $\Theta(n\text{ lg }n)$ 시간에 찾는 또다른 알고리즘으로, 앞에서 소개한 그레이엄의 스캔보다 구현이 간단한 편이다. 모노톤 체인(Monotone Chain)이라는 이름으로도 알려져 있다. 이 알고리즘은 점들을 정렬하는 기준을 각도 대신 좌표로 하며, 위쪽 껍질과 아래쪽 껍질을 따로 구하게 된다. 구체적인 작동 방법은 다음과 같다. 1. 점들을 $x$좌표가 증가하는 순서대로, $x$좌표가 같다면 $y$좌표가 증가하는 순서대로 정렬한다. 2. 점을 앞쪽부터 차례로 확인하면서 그레이엄의 스캔과 같은 방식으로 볼록 껍질을 찾는다. 마지막 점까지 확인하면 볼록 껍질의 윗부분이 완성된다. 3. 점을 뒤.. 98. Graham Scan 그레이엄의 스캔(그라함 스캔, Graham Scan)은 점 $n$개의 좌표가 주어졌을 때 $\Theta(n\text{ lg }n)$ 시간에 볼록 껍질을 찾는 알고리즘이다. 이 알고리즘은 기준점을 잡고 남은 점들을 각도 순으로 정렬한 다음 차례로 확인하는 방식으로 작동한다. 이전 글에 나온 점들의 볼록 껍질을 그레이엄의 스캔으로 구하는 과정은 다음과 같다. 이 블로그에서는 $x$좌표가 가장 작은 점, 그러한 점이 여러 개일 경우 그중 $y$좌표가 가장 작은 점을 기준점으로 했다.$x$좌표가 가장 작은 점 $1$을 기준점으로 잡고 나머지 점들을 각도 순으로 정렬한다. 그러면 점 $6$ - 점 $8$ - 점 $4$ - 점 $2$ - 점 $7$ - 점 $5$ - 점 $9$ - 점 $3$ 순서가 된다. 이제 이 .. 97. Convex Hull $2$차원 좌표평면에 $3$개 이상의 점이 존재하고 모든 점이 한 직선 위에 있지 않을 때, 이중 몇 개의 점을 선택한 뒤 이으면 볼록다각형이 되면서 나머지 모든 점이 다각형 내부에 존재하도록 할 수 있는데, 이 볼록다각형을 볼록 껍질(Convex Hull)이라고 한다. 다음 예시를 보자. 점들의 위치가 위와 같을 때 다음과 같은 볼록 껍질을 찾을 수 있다. 점들의 좌표가 주어졌을 때 볼록 껍질을 찾아내는 것 역시 기하 문제에서 종종 접할 수 있는데, 모든 선분 쌍을 하나씩 확인하는 등의 방법은 점의 개수가 많다면 비효율적이다. 다음 두 글에서 볼록 껍질을 빠르게 찾아내는 알고리즘에 대해 살펴볼 것이다. → solved.ac tag: convex_hull 이전 1 다음
