Graham Scan (1) 썸네일형 리스트형 98. Graham Scan 그레이엄의 스캔(그라함 스캔, Graham Scan)은 점 $n$개의 좌표가 주어졌을 때 $\Theta(n\text{ lg }n)$ 시간에 볼록 껍질을 찾는 알고리즘이다. 이 알고리즘은 기준점을 잡고 남은 점들을 각도 순으로 정렬한 다음 차례로 확인하는 방식으로 작동한다. 이전 글에 나온 점들의 볼록 껍질을 그레이엄의 스캔으로 구하는 과정은 다음과 같다. 이 블로그에서는 $x$좌표가 가장 작은 점, 그러한 점이 여러 개일 경우 그중 $y$좌표가 가장 작은 점을 기준점으로 했다. $x$좌표가 가장 작은 점 $1$을 기준점으로 잡고 나머지 점들을 각도 순으로 정렬한다. 그러면 점 $6$ - 점 $8$ - 점 $4$ - 점 $2$ - 점 $7$ - 점 $5$ - 점 $9$ - 점 $3$ 순서가 된다. 이제 이.. 이전 1 다음
