Algorithm: Convex Hull

#Polygon

           > 선분들로 이루어진 닫혀진 도형

           > n 개의 점 (x1,x2,...,xn) 과 n개의 선분 {ei|ei=(xi,x(i+1) and x(n+1)=x}가 다음 조건을 만족해야 한다

                     >> 두 선분 ei 와 e(i+1) 이 만나는 점은 v(i+1) 뿐

                     >> 그 외 다른 선분들은 만나지 않는다.

           > Convex Polygon ( 볼록 폴리건 )

                     >> 모든 내각 < 180 인 폴리건

 

#Convex Hull

           > n 개의 점이 주어졌을 때, 이 점을 모두 포함하는 가장 작은 볼록 다각형

                     >> 만들어진 볼록 다각형 안의 두 점을 잇는 직선은 항상 다각형 안에 있다.

#Brute-Force

           > 가장 y 좌표가 작은 점을 기준점으로 다른 모든 점이 선분 (u,v)의 왼쪽으로 가는 점 v를 찾는다.

           > v에서 다시 2번 조건을 만족하는 점을 찾는다

           > 위 두 방법을 반복해서 u로 돌아올때까지.

           > 시간복잡도: O(n^3)

 

#Graham Scan

           > 가장 y 좌표가 작은 점 u를 찾는다. (점 u는 convex hull 에 포함됨이 자명하다)

           > 다른 점들을 각에 따라 정렬

           > 정렬된 점들을 순차적으로 방문해 ccw알고리즘을 이용하여 convex hull 에 포함될 지 안될지 결정

           > 시간복잡도: O(n log n)

 

#Quick Hull

           > 가장 왼쪽 위의 점과 가장 오른쪽 아래의점, 그리고 이 둘을 이은 선분에서 가장 먼 점을 찾는다

                     >> 이 3점은 convex hull에 반드시 포함되며, 삼각형 내의 점들은 convex hull 에 포함될 수 없다.

           > 시간복잡도: 

                     >> Best: O(n log n)

                     >> Worst: O(n^2)