Convex Hull

00. 제한

원 위의 점들만 제시된 상황에서 (최적의 상황) Convex Hull을 구해야 한다고 생각해 보자. 이상적인 상황에서도 우리는 각도를 기준으로 정렬해야하므로 O(nlogn)이 걸린다. 이 문제는 O(n logn)보다 작을 수 없다. 

01. Brute-Force 1 : 선분 기준 방향성 판단

알고리즘 idea : 모든 선분 (nC2개)에 대하여 해당 선분이 Convex Hull위의 점인지 검사한다. 

Convex Hull인지 검사하는 방법은 모든 선분 O(n^2)에 대하여 다른 점들 n 개를 검사하는 방법이다. (O(n^3))

선분 하나에 점 하나이면, 점이 3개이다. 3개의 점에 대하여 CCV를 하여 n 점이 선분에 대하여 좌회전하는지 우회전 하는지 판단한다. 어떤 선분이 만약 모든 점들에 대하여 오직 좌회전이거나 오직 우회전이라면, 해당 선분은 Convex Hull 위의 점이라는 것을 알 수 있다. 

 

따라서 모든 선분에 대하여 (T(nC2)), 다른 모든 점들을 검사하므로 (T(n))

O(n^3)

02. Brute-Force 2 : 점 기준 방향성 판단

알고리즘 idea : 모든 점(n)에 대하여 다른 점들과의 방향성을 판단한다. 만약, 해당 점에서 다른 점들로 그은 선분들의 방향이 360도라면, 그 점은 convex hull 위의 점이 아니다. (convex hull 내부에 존재하는 점이다.)

만약 해당 점이 가지는 선분의 방향성이 180도 내부에만 있다면, 반대쪽 방향으로는 점이 존재하지 않는 것을 알 수 있다. 그러므로, 그 점은 convex hull 위의 점임을 알 수 있다. 

 

이런 식으로 모든 점에 대해 T(n), 다른 점과 비교하는 연산을 수행한다. T(n). -> O(n^2)

그리고 연산을 수행했을때, 다른 모든 선분과의 각도 관계가 180도 안이라면  그 점은 convex hull 위의 점이다. 

--> 다른 모든 선분과의 각도 관계가 180도 안인지 알기 위한 연산은 어떻게 수행되는 것인지 헷갈린다. sorting이 필요하다면 O(n^2logn)일텐데. 

 

 

03. Package Wrapping [Jarvis march 알고리즘]

알고리즘을 소개하자. 

가장 왼쪽의 점을 선택한다. 

해당 점을 다른 모든 점들과 검사한다. 

어떤 점과의 선분이 가장 왼쪽에 있는지 검사한다. 

가장 왼쪽의 선분과 연결되어 있는 점을 선택한다. (convex hull 위의 점) --- > 그리고 그 점에 대해서 다시 위의 과정을 수행한다. 

기존 점을 다시 만나는 순간이 오면, convex hull이 완성된 것이다. (?)

 

하나의 점을 다른 모든 점과 검사하므로 O(N^2)의 시간이 걸린다. (가장 왼쪽 or 가장 오른 쪽의 점을 선택할 때는 sorting 할 필요 없이 비교를 할때 선택하면 된다. 간략히 검사할 때(n을 돌때), max 값 찾는 선형 알고리즘 코드를 생각하면 좋을 것이다.)

 

.... sorting 과정이 빠진게 02번 brute force 에서 개선된 점인가 .. ? 

정확성은 loop invariant로 증명하면 될 것 같다. terminate 조건을 신경써야 할 듯 하다. 

 

04. Graham Scan

아주 재미있는 알고리즘이다. 드디어 "접선 구하기"의 아이디어가 사용된다. 

알고리즘 소개 

1. y축을 기준으로 가장 아래에 있는 점을 시작점으로 잡는다. (점 k라고 하자.)

2. 점 k에서 x축에 평행하게 직선을 그렸다고 해보자. 이 직선에 대하여 다른 점과의 각도를 기준으로 정렬해보자. (O(nlogn))

3. 정렬된 순서로 다른 점들을 아래의 순서에 맞게 검사한다.

3-1. 새로운 점과 직전의 점이 좌회전 관계인지 우회전 관계인지 검사한다. 

3-2. 지금까지 좌회전 관계의 점들만 선택해 왔는데, 우회전 관계의 점이 발생한다면, stack의 점들을 pop 하며 되돌아간다. 

3-3. pop을 하던 도중, 다시 좌회전 관계인 점을 발견한다면, 새로운 점을 stack에 넣고, 다시 진행한다. (다음 각도의 new 점에 대해 위 과정을 수행한다.)

 

- > 스택에 넣고 빼는 과정으로 인해, pop을 하여 되돌아 가는 과정은 최대 2*n번 발생하고, 시간은 O(1)이 걸린다. 돌아가는 경우가 제한되어 있기 때문이다. 그러므로 시간이 많이 소요되지 않음이 보장된다. 이미 pop된, 스택에 존재하지 않는 점들은 더이상 연산되지 않는다. 

- > 그리므로 정렬하는 과정으로 인한 O(n logn)이다. 

(접선은 항상 우회전하거나 항상 좌회전한다.)

 

05. Plane Sweeping

알고리즘 소개

오른쪽의 끝, 왼쪽 끝에서 진행된다. 

왼쪽 -> 오른쪽인 경우만 살펴보자. 

밀고 나가다보면, 새로운 점 event가 발생함을 알 수 있다. 

y를 기준으로 정렬된 AVL 트리에서 새로운 점에서 가장 가까운 두 점을 얻는다. 해당 점과 새로운 점 사이의 관계가 우회전에서 좌회전이 되는, 즉 접점이 되는 순간까지 밀고 나간다. 

 

 

 

 

06. Dynamic Case

 

07. Divide and Conquer

 

08. Farthest Point