Convex Hull

• Smallest convex polygon containing all the points
• 주어진 점들을 모두 포함하는 볼록한 다각형 중 가장 작은 도형을 구하는 문제
• convex hull을 그리면 영역이 나오므로 이미지 처리 등에 많이 응용된다.

“가장 작다”는 말은 너무 모호하다. 가로 세로의 길이가 5인 정사각형과 가로 10, 세로 2인 정사각형 중 누가 더 작은가? 다행히도 이 문제는 가장 작은 것과 면적이 넓은 것이 동일하므로 가장 작다고 표현해도 된다.

O(N^3)에 해결하는 방법부터 생각해보자. 모든 가능한 N^2개의 선분에 대해 이 선분이 convex hull 위에 있는지 테스트한다. 선분을 직선으로 늘리면 평면이 두 개로 나뉜다. 이때 모든 점이 한쪽 평면에 있으면 이 직선은 convex hull 위의 점이다.

기하 문제에서 귀찮음을 피하기 위해 많이 하는 가정

1. X 좌표가 같은 점이 존재하지 않는다.
2. Y 좌표가 같은 점이 존재하지 않는다.
3. 한 직선 위에 점이 3개 있는 경우는 존재하지 않는다.

CCW (Counter-Clock-Wise)

정말 많이 쓰는 tool. 세 점이 있을 때 점을 따라 이동할 때 좌회전하는지 확인하는 방법.

일단 이런 경우만 고려하자.

점 2와 3을 잇는 선분의 기울기가 점 1과 2를 잇는 선분의 기울기보다 크면, 즉 (y3-y2)/(x3-x2) > (y2-y1)/(x2-x1) 가 성립하면 좌회전하는 직선이다.

놀랍게도 아래처럼 좌회전 할 때도 성립한다. 그래서 좌회전 하는 모든 경우에 다 동작함.

그럼 다시 convex hull 문제로 돌아오자. N개의 점들 중 두 개를 골라 다른 모든 점들에 대해 CCW를 돌려 좌/우회전 여부를 파악한다. 만약 모두 좌회전하거나 모두 우회전한다면 두 점은 convex hull 상의 점이다.

O(N^3)시간에 해결할 수 있으나 너무 느리다. 더 빠르게 풀 수 있는 방법은 없을까?

Package Wrapping: O(N^2 logN)

O(N^2logN)에 푸는 방법. 각도 정렬이라는 방법을 사용한다.

Y좌표가 가장 작은 점을 찾고(sorting) 오른쪽으로 수평으로 반직선을 긋는다.

그리고 반직선을 다른 점과 만날때까지 반시계방향으로 움직인다.

이 점이 convex hull의 다음 점이 된다. 그러면 이 점을 어떻게 찾을까?

시작점을 제외한 모든 점을 시작점과 이루는 기울기에 대해 정렬한다.

점 하나를 추가할 때마다 NlogN의 시간이 걸리므로 전체 O(N^2logN)의 시간복잡도를 갖는다.

문제점은, 각도를 계산하면 arctan나 sin-1의 함수를 쓴다는 것이다. 그런데 이 함수들의 리턴 타입은 double/float이라 계산 오차가 있다. 그래서 기울기가 비슷한 경우에는 원하는 값을 얻지 못할 수 있다.

그래서 대부분 각도로 계산하지 않고 CCW를 사용한다. 두 점 중에서 어떤 값이 왼쪽, 오른쪽에 있는지 알기만 하면 되기 때문에 CCW로 좌회전/우회전 여부만 파악하면 된다.

CCW는 정수계산이므로 오차가 없다. 그리고 위에서 (y3-y2)/(x3-x2) > (y2-y1)/(x2-x1)를 굳이 풀어서 전개한 것도 나눗셈 때문에 오차가 생길 가능성을 없애기 위함이었다.

Graham Scan: O(NlogN)

Optimal한 방법. Closest pair를 찾기 위해서는 sorting을 해야 하기 때문에 NlogN의 시간이 걸렸다. Convex hull을 찾기 위해서도 마찬가지로 NlogN의 시간이 필요하다.

원점을 중심으로 하는 원 위의 점 N개를 그려보자.

이 점들의 convex hull을 구하면 convex hull에서 등장하는 순서는 각도에 대해 sort한 순서이다.

증명

convex hull을 이용해 sorting을 풀어보자. 3 8 2 6 5 7 9 1

먼저 max값을 구하고(O(N)), 배열의 값들을 다음처럼 각도로 변환한다.

3 --> (3/(max+1)) * 2π

좌표평면 상에서 원점을 지나고 기울기가 (3/(max+1)) * 2π인 직선을 긋고 이 직선과 원의 교점의 좌표(α, β)를 구해 3을 이 값으로 대체한다.

그리고 이 점들로 convex hull 문제를 푼다. 새로 구한 점들을 각도에 대해 정렬하고 다시 원본 배열로 돌아오면 원본 배열을 정렬한 것이 되는 셈이다.

그러니까 convex hull 을 풀면 sorting한 것이 되는 셈이고, convex hull을 NlogN보다 빠른 시간에 풀 수 있으면 sorting을 NlogN보다 빠른 시간에 할 수 있다는 것을 의미한다. 그런데 sorting은 아무리 빨리 해도 최소 NlogN의 시간이 걸리므로 convex hull도 최소 NlogN의 시간이 필요함.

다시 graham scan으로 돌아와서, 두 점을 고르는 과정까지는 package wrapping과 동일하다.

그 다음에 각도 순서대로 점을 따라가면서 greedy와 비슷한 방식으로 점을 추가할 것이다. stack도 사용할 거임.

stack에 1과 2를 push한 상태에서, 3도 연결했을 때 좌회전하는지 아닌지를 판별해 좌회전하는 경우 stack에 push한다. stack의 top 세 개가 좌회전하는지를 물어보는 것이다.

4번 점부터는 우회전을 하므로 stack의 top 두 개의 값과 4번 점이 좌회전 할 수 있을 때까지 stack을 pop한다.

sorting밖에 없기 때문에 NlogN의 시간이 걸린다. 세 점으로 좌회전이 가능해질 때까지 stack에서 pop하는 과정에서 모든 점은 stack에 r각각 한 번씩 push, pop 된다. 따라서 scan하는 데는 O(N)의 시간이 걸린다.

Plane Sweeping

가장 왼쪽, 오른쪽 점은 항상 convex hull 위의 점이므로 이 두 점으로 도형을 자르면 upper hull과 lower hull으로 나뉜다. 비슷하게 가장 위, 아래 점은 항상 convex hull 위의 점이므로 이 두 점으로 도형을 자르면 left hull과 right hull으로 나뉜다. 우리는 이 중에서 right hull에 대해서만 살펴보자.

현재 sweep line 아래의 위치에 왔을 때, 지금까지 본 점들의 right hull이 계산되어 있다고 믿자(수학적 귀납법). base case는 점이 세 개일 때 생기는 삼각형의 convex hull이다.

새로 추가되는 점은 지금까지 봤던 모든 점들보다 X 좌표가 크다(점이 매우 많다고 가정하고 convex hull을 곡선에 가깝게 그렸음).

이때 새로 추가된 점에서 convex hull으로의 접선을 그리면 그림과 같이 convex hull이 갱신된다.

그럼 접선을 어떻게 구할 수 있을까? 가장 쉬운 방법은 모든 점에 대해 다 계산해보는 것이다. 그러나 이 방법은 O(N^2)의 시간이 걸린다.

우리의 목표는 O(NlogN)에 convex hull을 구하는 것이기 때문에, N개의 점 하나마다 logN의 시간밖에 쓸 수 없다.

여담이지만 위쪽 접선과 아랫쪽 접선이 다 정의가 안 되는 경우도 있다.

그럼 이제 진짜로 두 개의 접선을 logN 시간에 구해보자.

이를 위해서는 왼쪽의 점들이 Y 좌표값을 기준으로 balanced BST에 저장되어 있어야 한다. 각 점은 양쪽 선분도 저장하고 있다.

먼저 위쪽 접선을 찾아보자. 새로 추가된 점보다 Y좌표가 작은 값을 가진 점이면 무조건 위로 가야 한다.

접선은 CCW를 사용해 구한다. 새로 추가된 점과 기존의 점(추가된 점보다 Y좌표가 큼) 을 연결하는 반직선을 긋는다.

convex hull 안을 뚫고 들어간 경우 더 위쪽의 값으로 찾아봐야 한다는 것을 의미한다. 그럼 뚫고 들어간다는 것은 어떻게 알 수 있을까?

각 점이 양쪽 선분을 저장하고 있으므로, 뚫고 들어간다는 것은 저장한 선분 중 아랫쪽 선분이 새로 그은 직선의 왼쪽에 있고 위쪽 선분이 오른쪽에 있다는 것이다.

뚫고 나올 때는 아래로 내려와야 한다.

접점을 찾았을 때는 위쪽 선분과 아랫쪽 선분이 모두 새로 그은 직선의 왼쪽에 있다.

접점을 찾고 나면 점들이 갖고 있는 선분과 convex hull을 업데이트한다.

정리하면, 윗 접선을 찾는데 logN, 아랫 접선을 찾는데 logN, insert하는데 logN, delete하는데 klogN의 시간이 걸린다. logN+logN+logN=3logN이므로 O(logN) 이라고 할 수 있지만 klogN은 따로 처리해줘야 한다. 그러나 전체적으로 봤을 때 모든 점은 convex hull에 딱 한 번만 추가되고 최대 한 번 제거되기 때문에 O(NlogN) 시간에 해결할 수 있다.

Graham Scan과의 비교

Plane sweeping이 상수 overhead도 있고 tree도 사용해야 하기 때문에 더 느리다. 그러나 일부분의 convex hull을 갖고 있기 때문에 일부의 convex hull이 필요한 문제를 푸는 경우에는 plane sweeping을 사용하는 것이 낫다.

Dynamic Case

점이 계속 추가되는 경우를 생각해보자.

추가될 때마다 NlogN의 시간을 들여 다시 계산할 수도 있지만, 이미 계산된 값들을 활용하면 시간을 줄일 수도 있을 것이다.

점이 convex hull의 안쪽에 추가되었다면 convex hull은 변하지 않는다. 어떻게 하면 점이 convex hull의 안쪽에 추가되었다는 것을 빠르게 알아낼 수 있을까? –> binary search를 이용하면 알 수 있다.

upper hull보다 아랫쪽에, lower hull보다 윗쪽에 있는지를 확인한다.

upper hull보다 아랫쪽에 있는 경우: 추가된 점에서 Y축 방향으로 올라가다가 convex hull을 만나면 점은 upper hull보다 아랫쪽에 있다.

그리고 선분과 CCW를 이용해 위/아래 여부를 판별한다.

upper hall보다 윗쪽에 있는 경우: plane sweeping에서처럼 접선을 구해 convex hull을 업데이트한다.

그래서 현재까지의 convex hull을 알고 있는 것도 나쁘지 않다.

Divide and Conquer

이번에는 upper hull만 그려보자.

D&C스럽게 반으로 나눠서 왼쪽 upper hull은 계산되었다 치고 오른쪽 upper hull도 계산되었다 치자. 그리고 각 upper hull은 array에 저장돼 있다.

공통 접선이 생기면 공통 접선 상의 점들만 array에 남기고 나머지는 제거한다.

binary search 한 번에 공통접선을 찾을 수 없으므로 왼쪽 hull의 아무 점에서나 오른쪽 hull으로의 접선을 찾는다. 그리고 그 접선이 어떻게 지나가는지를 살펴본다. 그리고 오른쪽 hull의 접점에서 그 직선을 바라본다!

오른쪽 접점에서 바라봤을 때 접선이 왼쪽 upper hull을 뚫었다면 그건 공통접선이 아니다. 만약 뚫고 지나갔다면 다음 번에는 왼쪽 upper hull에서 좀 더 Y값이 큰 점에서 오른쪽으로 upper hull으로 접선을 그리면 된다!

그럼 이제 시간복잡도를 계산해보자. 왼쪽 upper hull에서의 점 하나가 오른쪽 upper hull을 binary search 하면서 logN 시간을 쓴다. 그리고 공통접선 여부 판별 이후 왼쪽 upper hull이 값이 binary search로 이동하면서 logN 시간을 쓴다. 따라서 모든 점 N개에 대해 logN*logN의 시간을 쓰므로 전체 시간복잡도는 O(N*logN*logN)이다.

번외: Farthest Point

가장 먼 점은 어떻게 찾는가?

2차원에서 가장 먼 점을 찾는 것은 1차원에서처럼 O(N)에 해결할 수 없다. 그러나 convex hull을 구하면 가장 멀리 있는 두 점을 찾을 수 있다.

Idea: 평행한 직선 두 개를 양쪽에서 밀어붙이면 두 점과 부딪힐 것이다. 이 두 점이 farthest point의 후보가 된다. 직선의 기울기를 변화시키며(convex hull의 각도를 보면서 그 사이 값들로만 해보면 됨) 가능한 거리를 다 찾은 다음에 그 중에서 거리가 최대인 두 점이 가장 멀리 있는 두 점이다.