Divide and Conquer - Convex Hull

Convex Hull

• n개의 점에서 가장 바깥쪽을 잇는 볼록한 다각형
• 정렬이 필요하므로 O(nlogn) 보다 빠를 수 없다.
• upper hull : convex hull의 위쪽 부분, 물론 아래쪽 부분도 확인을 해야 한다.

---

1. Count - Clock - Wise (CCW)

• A(x1, y1)
• B(x2, y2)
• C(x3, y3)

 

• A - B - C의 기울기를 통해 회전 방향을 알 수 있다.
  단, 세 점이 한직선 위에 있는 경우는 고려 X

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 - O(n³) | O(n²logn)

선분에 포함된 두 점과 다른 모든 점들을 이어봤을 때,
같은 방향으로 회전한다면 Convex Hull의 일부다.
선분 n^2 * n 확인
⇒ O(n³)

한 점에 대해서 모든 점들로 선분을 이었을 때,
선분이 존재하는 범위의 각도가 180도 이하라면 Convex Hull의 일부다.
각도를 기준으로 정렬 필요. → nlogn
⇒ O(n²logn)

---

3. Package Wrapping - O(n²)

1. y좌표가 가장 작은 점은 Convex Hull에 무조건 들어간다.
    이 점을 기준으로 삼자.
2. 각 점마다 각도순으로 정렬하여 가장 왼쪽, 혹은 오른쪽에 있는 점을 찾아서 연결.
3. 그 점에서 다시 왼쪽, 혹은 오른쪽에 있는 점을 찾아 반복하여 연결.
⇒ 정렬 필요 없이 단순 선택. O(n²)

 

---

4. Graham Scan - O(nlogn)

1. y좌표가 가장 작은 점은 Convex Hull에 무조건 들어간다.
   이 점을 기준으로 삼자.
2. 각도 순으로 정렬한 뒤 순서대로 점을 보며 좌회전이면 계속 스택에 Push 한다.
3. 다음 점을 연결할 때 우회전 한다면 그 점을 잇는 이전 점이
    좌회전이 될 때까지 지금까지 추가한 점들을 스택에서 Pop 하고
    그다음점을 스택에 넣는다.
4. 모든 점에 대하여 반복한다.
⇒ O(nlogn)

 

---

5. Plane Sweeping - O(nlogn)

• 왼쪽에서 오른쪽 점들을 쓸고 지나가면서 확인하는 방법

1. 이미 중간 까지는 완성된 Hull, 의 오른쪽 부분 Right Hull 이 있다고 가정.
    hull 위의 점들은 AVL Tree에 y좌표로 정렬되어 들어있다.
2. 외부의 새로운 점을 Hull에 추가하려면 그 점으로부터 Hull로의 접선을 찾는다.
    (접선은 Hull의 위아래로 생긴다.)
    a. 외부의 점에서 Hull로 수평선을 긋는다.
    b. 이진 탐색을 통해 수평선 위쪽에 존재하는 Hull 위의 점을 찾는다.
    c. 좌회전이 될 때까지 다음점으로 이동한다.→ O(logn)
        y 좌표로 정렬되어 있기 때문에 다음점은 이전점보다 y좌표가 크다. (Hull 위쪽 기준)
    d. 그 점과 외부 점을 이으면 접선이 된다.

3. 그 접선이 right Hull의 새로운 선분이 된다.
    옛날점들은 이미 삭제하고 난 뒤이므로 고려할 필요가 없다.
4. 위 아래로 접선을 모두 찾아 Hull을 결정한다.
⇒ AVL 트리를 사용하면 O(nlogn)

 

---

6. Dynamic Case

• 완성된 Convex Hull이 있을 때 새로운 점이 추가된다면?

1. Convex Hull 안쪽에 추가되는 점은 상관없다.
    AVL 트리를 사용해서 안쪽인지 판별 가능 → O(logn)

2. Upper Hull 위쪽에 새로운 점이 추가된다면
    Plane Sweeping 에서와 똑같이 접선을 찾아서 Hull을 결정하면 된다.

 

---

7. Divide and Conquer - O(log²n)

1. Divide 해서 left upper hull과 right upper hull 이 있다고 가정하자.
2. left와 right의 공통 접선을 찾고 그 안쪽의 점들은 버리면 된다.
    a. left hull 위의 아무점을 기준으로 잡는다.
    b. right hull 방향으로 ray를 쏜다.
    c. ray에서 가장 먼저 만나는 점은 좌회전을 해서 다음점(오른쪽)으로 이동.
        다음점으로 이동할 땐 이동하기 전인 옛날 점은 삭제한다. ⇒ O(nlogn)
    d. ray에서 나중에 만나는 점은 좌회전을 해서 이전점(왼쪽)으로 이동.
        다음점으로 이동할 땐 이동하기 전인 옛날 점은 삭제한다. ⇒ O(nlogn)
    e. 반복해서 다음점과 이전점이 일치하는 즉, right hull의 접점을 찾는다.
        그 점을 새로운 기준으로 삼는다. ⇒ O(logn)
    f. right hull의 접점에서 다시 left hull로 ray를 쏜다.
    g. 위를 반복해서 다시 left hull의 접점을 찾는다.⇒ O(logn)
    h. right hull의 접점과 left hull의 접점을 이으면 그것이 접선이다.

3. 접선은 Divide 된 두 hull을 연결해서 하나의 hull로 만드는 선분이 된다.
⇒ O(log²n)

 

---

8. Farthest Point - O(n)

• 두 점 사이의 가장 먼 거리

1. Convex Hull을 구한다.
2. Hull 위의 모든 점들에 대해서 Rotating Caliper를 한다. ⇒ O(n)
    a. Hull 위의 양 끝 두 점을 시작으로 잡고 캘리퍼스를 설치한다.
    b. 캘리퍼스를 반시계 방향으로 회전하면서 각도가 더 작은 점을 끝 점으로 바꿔준다.
    c. 캘리퍼스 사이의 거리는 회전할 때마다 큰 값으로 항상 따로 갱신해 준다.

3. 다시 처음으로 돌아왔을 때 사이의 거리가 가장 컸던 값이 답이다.