볼록 껍질을 만드는 방법을 배우기 전에, 볼록 껍질을 이용하여 풀 수 있는 몇 가지 문제를 살펴봅시다.
이 글에는 그림이 많이 부족하지만, 여러분의 상상력을 믿겠습니다.
#점 위치 판별
볼록 다각형 $A_0 A_1 A_2 \ldots A_n$이 있고, 점 $P$가 그 내부에 있는지 판별하라는 쿼리가 들어온다고 합시다.
이 다각형을 삼각형 $\Delta A_0 A_1 A_2, \Delta A_0 A_2 A_3, \ldots, \Delta A_0 A_{n-1} A_n$으로 삼각분할한 것을 생각하고, 조금 더 어려운 문제를 풀어 봅시다. 바로 점이 (애초에 다각형 내부에 있다면) 이 삼각형들 중 어느 것에 속하는지 판별하는 문제입니다.
벡터 $\overrightarrow{A_0 A_1}, \overrightarrow{A_0 A_2}, \ldots, \overrightarrow{A_0 A_n}$, 즉 다각형을 삼각형들로 분할하는 대각선들을 생각해 봅시다. 이 벡터들은 각도 순으로 정렬되어 있다는 점에 주목하십시오. 명확히 하기 위해 반시계 방향으로 정렬되어 있다고 가정하겠습니다. 벡터 $\overrightarrow{A_0 P}$를 생각하고, $n-1$개의 벡터로 이루어진 이 수열에서 $\overrightarrow{A_0 P}$의 «오른쪽»에 있는 첫 번째 벡터를 찾읍시다. 이는 이진 탐색과 벡터 곱셈의 부호를 이용한 확인으로 할 수 있습니다.
벡터 $\overrightarrow{A_0 P}$가 $\overrightarrow{A_0 A_i}$와 $\overrightarrow{A_0 A_{i+1}}$ 사이에 끼어 있는 $1 \leq i < n$을 찾았다고 합시다. 그러면 점 $P$가 삼각형 $\Delta A_0 A_i A_{i+1}$ 안에 들어가는지 아닌지만 확인하면 됩니다. 들어간다면 점 $P$는 다각형 내부에 있으며 그 위치를 찾아낸 것이고, 그렇지 않다면 점 $P$는 다각형 외부에 있습니다.
이러한 각 쿼리는 $O(\log{n})$ 시간에 처리합니다.
#주어진 직선에 평행한 접선 찾기
볼록 다각형과 어떤 직선이 하나 주어졌다고 합시다. 우리는 다각형에 접하면서 주어진 직선과 평행한 직선 $2$개를 찾고자 합니다.
이 직선들이 다각형에 접하는 점을 찾아봅시다. 주어진 직선의 방향 벡터인 벡터 $v$를 생각해 봅시다. 벡터 $\overrightarrow{A_0 A_1}, \overrightarrow{A_1 A_2}, \ldots, \overrightarrow{A_n A_0}$를 생각해 봅시다. 꼭짓점들이 반시계 방향 순서로 주어진다는 점을 다시 떠올리면, 이 벡터들은 극각을 기준으로 정렬되어 있습니다.
그러면 이 순서에서 벡터 $v$와 $-v$가 어떤 인접한 위치들 사이에 놓여야 하는지 살펴보면, 그 위치들은 접선이 다각형에 접하는 꼭짓점들에 대응합니다. 이 위치들을 찾으려면 벡터들의 수열에 대해 lower_bound를 수행하면 충분합니다.
#점에서 접선 찾기
이번에도 볼록다각형 $A_0 A_1 \ldots A_n$이 주어지지만, 직선은 없고 대신 어떤 점 $P$가 주어진다고 합시다. 직선 $P A_i$와 $P A_j$가 다각형의 접선이 되도록 하는 $2$개의 점 $A_i$와 $A_j$를 찾거나, 점 $P$가 다각형 내부에 있다고 판정하려 합니다.
검사는 이미 $O(\log n)$에 수행할 수 있으므로, 점이 외부에 있다고 가정합시다.
같은 방향 벡터-변의 수열을 생각하고 이를 두 부분으로 나눕시다. 점 $A_{i+1}$이 직선 $P A_i$의 왼쪽에 있으면 변 $A_i A_{i+1}$을 왼쪽 변이라 하고, 그렇지 않으면 오른쪽 변이라 하겠습니다.
다음으로 왼쪽 절반에서 이진 탐색을 실행하여, $A_{i+1}$이 벡터 $P A_i$의 오른쪽에 놓이는 첫 번째 꼭짓점 $A_i$를 찾을 수 있습니다. 접선은 바로 이 꼭짓점에 접합니다. 오른쪽 절반에서의 이진 탐색도 같은 방식으로 수행합니다.
#가장 멀리 떨어진 두 점
$n$개의 점이 주어질 때, 그중에서 서로 가장 멀리 떨어진 점의 쌍을 찾아야 합니다.
최적의 쌍은 반드시 이 집합의 볼록 껍질 위에 놓여 있다는 점에 주목합시다. 만약 두 점 중 하나가 볼록 껍질의 내부에 엄격하게 놓여 있다면, 그 점 대신 더 멀리 떨어진 다른 점을 선택할 수 있기 때문입니다.
모든 점의 볼록 껍질을 구하고, 그 꼭짓점들에 반시계 방향 순회 순서대로 번호를 매깁시다. $l$번째 점에서 가장 먼 점이 $r$번째 점이었다면, $(l+1)$번째 점과 그 이후의 모든 점에 대해서는 순회 순서상 $r$번째 점보다 앞선 어떤 점도 최적이 될 수 없다는 점에 주목하십시오.
여기서 투 포인터 기법을 적용하는 아이디어가 떠오릅니다. 껍질 위의 점 $l$을 순회하면서 그에 대한 최적의 $r$을 유지하고, while 반복문에서 쌍 $l$과 $(r+1)$에 대한 답이 더 나은지 확인합니다. $r$은 전체적으로 최대 $O(n)$번 증가하므로, 알고리즘은 $O(n)$에 볼록 껍질을 구성하는 시간을 더한 시간에 동작합니다.
#최대 넓이의 삼각형
$n$개의 점이 주어질 때, 그중에서 넓이가 최대인 삼각형을 찾아야 합니다.
이전 문제와 마찬가지로, 세 점은 모두 반드시 볼록 껍질 위에 있으므로 곧바로 볼록 껍질을 구성합시다.
이제 고정된 밑변 $a$와 $b$에 대해, 밑변의 오른쪽 점을 증가시키면 최적의 세 번째 점 $c$의 번호는 감소하지 않는다는 점에 주목합시다.
따라서 점 $a$를 순회한 다음, 두 포인터 기법을 사용하여 최적의 $c$를 유지하면서 $b$를 순회할 수 있습니다. 전체적으로 알고리즘은 $O(n^2)$에 동작합니다.