Convex Hull 이란 평면 좌표에서 어떤 점들이 있을 때 모든 점들을 포함 하는 가장 작은 볼록 다각형을 의미한다.
(점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형)
점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 O(nlog n)보다 빠를 수 없다.
1. Count - Clock - Wise (CCW)
이 알고리즘은 세 점이 관계를 표현할 때 유용하다.
A(x1,y1), B(x2,y2), C(x3,y3)가 있다고 해보자.
A와 B의 기울기 + B와 C의 기울기를 가지고 회전 방향을 알 수 있다.
- A와 B의 기울기 > B와 C의 기울기 → 우회전
- A와 B의 기울기 < B와 C의 기울기 → 좌회전
- A와 B의 기울기 = B와 C의 기울기 → 한 직선
하지만 수업에서는 세 점이 한직선에 있는 경우는 고려하지 않는다.
식을 써서 정리해보면
- (x2-x1)(y3-y2) - (y2-y1)(x3-x2) > 0 → 좌회전
- (x2-x1)(y3-y2) - (y2-y1)(x3-x2) < 0 → 우회전
2. Brute-Force-ish
2.1 Brute-Force-ish(1) - n^3
모든 선분마다 Convex Hull 의 일부인지를 판단하는 알고리즘이다.
선분에 포함된 두 점과 다른 모든 점들을 각각 이어봤을 때, 모두 같은 방향으로 회전하면 Convex Hull의 일부이다.
점은 n개이기 때문에
모든 선을 그으면 n^2이 되고 경계선에 있는지 n번 확인 해야한다.
경계선인지 확인 하는 방법은 다른 모든 점이랑 CCW를 해서
모두 우회전이거나 모두 좌회전이면 경계선에 있다고 판단한다
2.2 Brute-Force-ish(2) - O(n^2logn)
특정 점이 Convex Hull 에 포함되는 꼭짓점인지를 판단하는 알고리즘이다.
한 점에 대해서 모든 점들로 선분을 이었을 때, 선분이 존재하는 범위의 각도가 180도 이하라면 Convex Hull 에 포함되는 점이다. 이 경우 각도를 기준으로 Sorting이 해야하므로 O(nlogn)이 소요된다.
3. Package Wrapping - O(n^2)
Convex Hull 위에 있는 것이 보장된 점 (ex. y좌표가 가장 작은 점) 위에서 시작한다.
각 점마다 모든 점들 중 가장 왼쪽 or 오른쪽에 있는 점을 찾아서 연결하고,
그 점에서 다시 왼쪽 or 오른쪽에 있는 점을 찾아 반복하여 연결하면 된다.
이 경우 Sorting 할 필요 없이 바로 비교를 시작하여 매 쌍마다 오른쪽 or 왼쪽 에 있는 점을 고르면 된다.
따라서 O(n^2) 만큼 시간이 걸린다.
4. Graham Scan - O(nlogn)
기본적인 원리는 각도순으로 점을 보며 스택에 넣다가,
다음 점을 연결할 때 우회전할 경우, 다시 좌회전이 되도록 지금까지 추가한 점들을 스택에서 제거하는 것이다.
알고리즘 자체는 모든 점들이 스택에 push/pop만 수행하므로 O(1)밖에 안걸리고,
점들을 정렬하는데는 O(nlogn) 시간이 걸린다.
5. Plane Sweeping - O(nlogn)
위 그림과같은 right hull이 있다고 해보자.
(왼쪽 점 두개는 무시해도된다)
Balanced Tree에 hull 위에 있는 점이 y정렬으로 들어있다.
새로 점이 들어오면 점으로부터 접선을 찾아야한다.
더 보기좋은 예를 봐보면
위 그림과 같다.
추가되는점으로부터 접선을 두개 찾을 수 있다.
접선은 어떻게 찾을 수 있을까?
위 그람을 보면 뚫고 들어가서 뚫고 나온다.
뚫고 들어가는 점을 보면 다음점에서 좌회전 이전점에서는 우회전이다.
이 경우에는 이전점 쪽으로 더 이동해야한다.
뚫고 나가는 점을 보면 이전 점에서 좌회전 다음점에서는 우회전이다.
이 경우에는 다음점 쪽으로 더 이동해야한다.
이는 Balanced Tree이기 떄문에 위의 정보를 이용하여 binary search 하듯이 접점을 찾을 수 있다.
접선 두개를 찾으면 그 사이의 x 한 곳을 삭제하면 된다.
위쪽 접선 찾는데에 O(log n)
아래쪽 접선 찾는데에 O(log n)
insert O(log n) -> 처음 등장했을 때 한 번 추가
delete O(n log n) -> 한번 제거될 수 있음. 한 점마다 search하는 비용만 들어서 logn 씩 든다
각 점은 한 번 추가되고 최대 한 번 제거된다.
→ n logn
모두 balance tree에 들어있기 때문에 가능하다.
6. Dynamic Case
위 그림처럼convex hull을 n log n으로 계산했다고 가정해보자
안쪽에 추가되는 점은 convex hull과 상관없다.
하지만 안쪽에 추가되었다는 사실을 어떻게 알 것인가?
새로 들어온 점도 balance tree에 넣어보면 이를 무시할 수 있는지 없는지 알 수 있다.
upper hull위에 있다면 (밖에 있다면)
앞에 right hull처럼 접선 두개를 긋고 그 사이 점을 없애면 된다.
7. Divide and Conquer - O( log^2n)
반 나눠서 왼쪽 upper hull과 오른쪽 upper hull이 계산되었다고 친다.
각각은 array에 저장했다고 생각 tree에 넣고 생각할 수 있지만 O(n)
=> 위쪽 공통 접선을 찾는다
중간은 버리고 공통접선을 긋고 해당되는 애들만 새로 array에 저장한다.
그럼 어떻게 접선을 찾을까?
우리는 여기서 O(n)을 쓸 수 있다.
왼쪽에서 아무곳에 점을 놓고 오른쪽에 아무 점을 찍는다.
뚫고 나가는지 나가지 않는지를 확인하며 접선을 찾는다. (BST)
다른 곳(오른쪽)에서 반대쪽(왼쪽)을 다시 본다.
뚫고 나가는지 나가지 않는지를 확인하며 접선을 찾는다.
오른쪽 점 하나가 log n시간을 쓰고 왼쪽 점 하나도 log n시간을 쓴다.
(log n개의 점을 왼쪽에 찍으며 찾는다.)
→ O( log^2n)
8. Farthest Point - O(n)
Convex hull을 이용하면 가장 먼 점도 찾을 수 있다.
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] Dynamic Programming : Fibonacci Number (0) | 2022.10.18 |
|---|---|
| [ 알고리즘 ] Matrix Multiplication, Strassen Alg, Karatsuba Alg (0) | 2022.10.18 |
| [ 알고리즘 ] Closest pair (0) | 2022.10.17 |
| [ 알고리즘 ] Median Problem (0) | 2022.10.17 |
| [ 알고리즘 ] Divide and Conquer : Quick Sort (0) | 2022.10.15 |