14. convex hull [6 2주차]

14. Convex Hull [6-2주차]

2024년 1월 13일 토요일

오후 10:48

<Convex Hull>

2차원 평면의 점들의 좌표들이 주어졌을 때, 점 몇개를 이어 도형을 만든 뒤, 그 도형 안에 모든 점이 들어가도록 한다.

 

 

단, 도형의 내각은 180도 이하여야 한다. 도형이 볼록 다각형이여야 함.

 

점들 바깥에 고무줄을 둘렀다고 생각할 수 있다.

 

포토샵 등에서 사물의 외곽선을 따는 데 사용됨.

 

 

<CCW (Counter-Clock-Wise)>

 

 

Convec Hull 문제에서 볼록 다각형이 되려면 도형의 둘레가 한쪽 방향으로만 꺾여야 한다. 점들을 이은 선이 왼쪽으로 꺾이는지 오른쪽으로 꺾이는지 판단하는 알고리즘이 필요하다.

 

컴퓨터의 부동소수점 연산이 부정확하므로, 오차 때문에 왼쪽으로 꺾이는 경우가 오른쪽으로 꺾인다고 나올 수도 있다.

따라서 CCW 알고리즘에서는 정수 연산으로 점들이 어느 방향으로 꺾이는지 판단한다.

 

 

 

<Convex Hull O(n³)>

두 점을 골라 나머지 n-2개 점들에 대해 좌회전인지 우회전인지 계산한다. 만약 n-2개 점이 모두 좌회전이거나 모두 우회전이라면, 두 점은 convex hull에 포함된다.

 

 

두 점을 고르는 경우의 수는 _nC₂ = O(n²), 각 두 점마다 n-2개의 점과 CCW 연산을 하므로, 시간복잡도는 O(n³) 이다.

 

 

<Convex Hull의 최소 수행 시간>

최소 실행 시간은 O(nlogn)이다. 원 둘레에 점이 있는 경우, 알고리즘은 점들을 정렬하는 시간이 걸리기 때문이다.

 

 

<Convex Hull O(n²)>

각각의 점 p마다 연산을 수행한다. 점 p와 나머지 점들을 잇는 n-1개의 선분을 그린다. 점p를 지나는 직선 L에 대해, L의 한쪽 평면에만 선분들이 존재할 수 있는 경우, 점 p는 convex hull에 들어간다. 이 방법을 사용하면 O(n²)이 걸린다.

 

 

<Package Wrapping>

y좌표가 가장 작은 점은 무조건 convex hull에 들어간다. 이를 p1이라 한다. p1을 지나는 직선을 그은 뒤 반시계 방향으로 회전시킨다. 이 직선이 처음으로 만나는 점을 p2라 한다. p2에 대해서도 직선을 긋고 반시계 방향으로 회전하여 p3를 찾는다.

이는 O(n²)이 걸린다.

 

 

<Graham Scan>

점들의 집합 Q가 입력으로 들어온다.

Convex Hull의 집합을 CH(Q)라 하고, 스택 S에 CH(Q) 의 후보를 저장하자.

 

1.     y좌표에서 가장 아래에 있는 점을 p0 라 한다.

2.     p0를 제외한 나머지 점 p에 대해, 벡터 p0->p의 각도를 구한다. 이를 n-1 개의 점 모두에 수행한다.

3.     p0->p의 각도에 대해 오름차순 정렬한 배열

A = [p1, p2, p3, …, pm] 을 구한다.

각도가 같은 점이 있다면, p0로부터 가장 먼 점만 남기고 나머지는 배열에서 지워도 된다.

4.     스택 S에 p0, p1, p2를 순서대로 push 한다.

5.     for i = 3 to m

while S의 위에서 두번째 요소, 첫번째 요소, pi 가 이루는 각이 좌회전하지 않음

pop(S)

push(pi)

 

6.     for 루프가 끝나면, 스택 S는 CH(Q)가 된다.

 

 

 

<Graham Scan의 시간복잡도>

1.     p0를 찾는 데 O(n)이 걸림.

 2, 3. 각도를 기준으로 점들을 정렬하는 데 O(nlogn)이 걸림.

4.     스택에 p0, p1, p2를 push하는 데 O(1)이 걸림.

5.     for문은 최대 n-3번 실행. push하는 데 O(1)이 걸림.

따라서 for 문은 while 부분을 제외하면 O(n)이 걸림.

6.     while루프는 실행 전체에서 n번 미만 반복되고, 회전 연산과 pop에는 O(1)이 걸리므로,

while루프는 총 O(n)이 걸린다.

 

따라서 Graham 알고리즘의 수행시간은 O(nlogn)이다.

 

 

<Plane Sweeping>

왼쪽의 수직선을 오른쪽으로 이동시킨다.

직선의 왼쪽 점들에 대해, 오른쪽 convex hull이 구해져 있다고 가정한다.

 

 

 

 

 

오른쪽 convex hull : convex hull을 가장 위의 점과 가장 아래의 점을 기준으로 두 개로 나누었을 때, 오른쪽 부분.

 

직선이 새로운 점을 만날 때마다 알고리즘을 수행한다. -> 점을 x좌표 기준으로 정렬하여 구현

새로운 점 p에 대해, 이전에 구해진 convex hull로 접선 2개를 그린다.

접선 사이에 점이 있으면, 그 점은 버린다.

 

접선의 접점은 어떻게 구하는가?

오른쪽 convex hull에 있는 점들을 y좌표 기준으로 AVL트리에 저장해 둔다.

AVL 트리에서 이진 탐색을 하며 접선을 구하게 된다.

 

위쪽 접선을 구하는 과정을 살펴보자.

이진 탐색을 통해, 오른쪽 convex hull에서 점 p의 바로 위에 있는 점 a를 찾는다.

오른쪽 hull에서 a위의 점은 b, b위의 점은 c라고 한다.

 

p, a, b에 대해서 CCW연산을 한다. 우회전인 경우 a의 위에 점에 대해 CCW연산을 반복한다. 즉, p, b, c에 대해 CCW연산을 한다. 이 과정을 반복하여 처음으로 좌회전이 되는 점 p'을 찾는다. p'이 위쪽 접점이다.

 

아래쪽 접점도 비슷한 방법으로 구한다. 처음으로 우회전이 되는 점 p''을 찾으면 된다.

 

다음으로, p'와 p''사이의 점들을 AVL트리에서 제거하고, p를 AVL트리에 넣는다.

수직선이 마지막 점을 지나면, AVL트리가 오른쪽 convex hull 정답의 집합이 된다.

 

왼쪽 convex hull은 수직선을 왼쪽으로 이동시키며 마찬가지 방법으로 구한다.

 

 

AVL트리에서 탐색하는 데 O(logn)이 걸리고, 수직선이 n개의 점 각각을 지날 때 마다 탐색을 하므로, 탐색은 총 O(nlogn)이 걸린다. AVL 삭제 연산도 O(logn)이 걸리고, n개의 점이 한 번 이상 삭제되지 않으므로, 삭제 연산에는 총 O(nlogn)이 걸린다. 따라서 시간복잡도는 O(nlogn)이다.

 

 

<Dynamic Case>

Convex Hull을 이미 구한 상태에서, 점 p가 추가되는 경우, O(logn) 시간 안에 새 Convex Hull을 구해 보자.

 

먼저 이전 Convex hull 을 구하는 과정에서, upper hull과 lower hull을 각각 x좌표 기준 AVL트리 (총 2개)에 저장해 두어야 한다.

 

p로부터 수직선을 긋고, 수직선이 upper hull과 lower hull과 만나는 두 변을 구한다.

이를 이용해 p가 두 변 사이에 있으면 무시하고, 바깥에 있으면 접선을 구할 것이다.

여기서는 upper hull을 기준으로 설명할 것이다.

 

수직선과 upper hull이 만나는 변을 이루는 두 점을 AVL 트리에서 구해, p가 변 아래에 있는지 확인한다. 아래에 있다면 upper hull에서의 실행 과정은 멈추고, lower hull 에서의 연산을 시작한다.

(lower hull 위에 있다면 p는 무시, 아래에 있다면 접선을 구함)

 

p가 upper hull 위에 있다면 접선을 구한다.

 

 

왼쪽 접선 : 처음으로 좌회전이 되는 점, 오른쪽 접선 : 처음으로 우회전이 되는 점

 

점 p가 이전에 구한 convex hull의 왼쪽이나 오른쪽에 존재한다면, Plane Sweeping에서의 방법으로 구하면 된다.

 

 

<Divide and Conquer를 이용한 알고리즘>

Divide and Conquer를 이용해 upper hull을 구하는 방법을 살펴보자.

 

 

먼저 점들을 x좌표로 정렬하고 좌우로 나눈다. 좌우 점들의 집합 각각에 재귀 호출하여 upper hull 두 개를 구한다.

결합할 때는 두 upper hull의 공통접선을 찾으면 된다.

공통접선은 어떻게 찾는가? ( O(n)시간 안에 찾아야 한다 )

 

 

왼쪽 hull의 점을 아무거나 하나 선택하고, 오른쪽 hull로의 접선을 찾는다. 이때, 접선은 CCW와 이진 탐색을 이용해 찾는다. -> O(logn) 시간이 걸림

그렇게 오른쪽 접점이 결정되면, 그 오른쪽 접점으로부터 왼쪽 hull에 그은 접선도 이진 탐색을 통해 찾는다.

이러한 과정을 반복하면 O((logn₎²₎시간에 공통 접선을 찾을 수 있다.

 

 

<Farthest Point>

가장 거리가 먼 점의 쌍을 찾는 방법.

가장 거리가 먼 점의 쌍은 Convex Hull 위에 있다.

convex hull 양옆에서 평행한 직선 두 개를 좁혀오는 식으로 거리를 계산한다.

 

 

평행한 직선의 각도를 바꿔가며 거리 계산을 반복한다. 그중 가장 긴 거리가 Farthest Point의 거리이다.

 

각도는 각 점마다 하나씩 대응되며, 총 O(n)개의 각도로 검사하면 된다.