2006 IMOSL G10과 Rotating Calipers 알고리즘

2차원 평면 상에서 가장 먼 두 점을 구하는 알고리즘으로는 Rotating Calipers가 잘 알려져 있다. 이는 볼록 껍질 상에서 한 점 A를 고정한 채로, 거리가 최대가 되도록 다른 점 B를 움직이는 과정을, A를 한 칸씩 움직이면서 반복하는 것이다. 즉 투 포인터 알고리즘이라고 할 수 있다. 그런데 나는 투 포인터를 사용할 때면 실수를 굉장히 많이 하는 편이다. 왜냐하면 어떤 점을 먼저 이동해야 하는지를 거리의 대소에 따라 경우를 잘 나누어 주어야 하기 때문이다. 그런데 수학 올림피아드 문제를 풀다가 우연히 Rotating Calipers 알고리즘을 병합 정렬의 관점에서 생각하며, 또 그 결과를 보다 직관적으로 하나의 도형으로 표현하는 방법을 알게 되었다.

*주의: 글 중간에 넣어놓은 영어로 된 IMO Shortlist 원문은 안 읽어도 된다. 보다 엄밀한 증명을 원하는 사람이 있거나, 내가 수학적인 서술 방식을 알아둘 필요가 있을 때 참고하고자 넣어둔 것이다.

 

2006 IMOSL G10

2006년도 IMO Shortlist 기하 영역의 마지막(가장 어려운) 문제인 G10의 Solution 2를 읽으면서 이 아이디어를 생각하게 되었다. G라는 레이블이 붙어 있지만 조합적인 느낌이 상당하다. 실제로 C7도 조합기하인데, C7은 조합이고 G10은 기하인 이유는 C7은 3차원이고 G10은 2차원이어서가 아닐까 생각해 본다.

 

문제 Statement: 주어진 볼록다각형의 각 변 a에, a를 한 변으로 하고 다각형에 포함되는 삼각형의 최대 넓이를 할당한다. 각 변에 할당된 넓이의 합은, 다각형의 넓이의 두 배 이상임을 보여라.

 

알고리즘을 공부하는 입장에서는, 문제를 읽는 순간  'a를 한 변으로 하고 다각형에 포함되는 삼각형의 최대 넓이'를 구하기 위해서는 a에서 거리가 가장 먼 점을 찾아야 하므로, Rotating Calipers 알고리즘을 이용해서 a를 돌리면서 구하면 됨을 인지하게 된다. 그런데 이 문제는 단순히 구하는 알고리즘적인 과정을 넘어서, 할당된 넓이에 대한 수학적 성질을 증명해야 한다. Rotating Calipers 알고리즘으로 구한 할당된 값들을 직접 수학적 증명으로 사용하기는 어려울 것이다. 그러므로 이를 보다 직관적으로 표현해야만 한다. Solution 2는 이를 표현하는 기가 막힌 아이디어를 제시하고 있다.

 

Official Solution 2의 시작 부분

길게 써 있지만, 쉽게 한줄로 표현하면 이렇다: "볼록다각형 P의 각 변의 양방향에 해당하는 벡터들을 방향순으로 정렬한 후에 차례대로 이어붙여서 만든 볼록다각형을 Q라고 하자"

 

이 문제의 풀이에서 중요하게 사용되는 보조정리는 다음과 같다.

보조정리와 그 증명

"P의 각 변에서 가장 먼 점 까지의 거리의 두 배는, Q의 상응하는 변들 사이의 거리와 같다"이다. 실제로 수학 올림피아드에 출제된다면 위와 같이 단위 벡터와의 내적을 이용해서 엄밀하게 서술해야 할 것이다. 그러나 직관적으로 설명하자면 다음과 같다.

i번 점과 i+1번 점을 잇는 선분에서 가장 먼 점이 k이다.  i+1부터 k까지 시계 반대 방향으로는 파란색 변들이고, k부터 i까지 시계 반대 방향으로는 빨간색 변들이다.

위 그림과 같이 P가 있을 때, 밑변의 오른쪽에서 왼쪽이 나올 때까지 거치는 선분들을 생각해 보자. 방향이 그 둘 사이에 있어야 하므로, 파란색 선분들은 시계 반대방향(올라가는 쪽)으로 한 번씩 거친다. 빨간색 선분들은 시계 방향(올라가는 쪽)으로 한 번씩 거친다. 그러면 이 둘의 합으로는 세로 방향으로는 총 $2h_i$만큼이 올라가므로, 보조정리가 증명되었다.

 

이 보조정리는 문제의 해결에서 중요한 역할을 한다. 왜냐하면 'a를 한 변으로 하고 다각형에 포함되는 삼각형의 최대 넓이'를 단순히 'Q에서 a를 밑변, 대칭중심을 꼭짓점으로 하는 삼각형의 넓이'로 바꾸어주기 때문이다. (Q는 모든 벡터들이 다른 방향으로 두 번씩 있으므로, 점대칭 도형이어서 대칭 중심이 존재한다.) 이렇게 하면 문제에서 주어진 합이 Q의 넓이의 1/2임을 알 수 있어서, 이후 Q의 넓이가 P의 4배 이상임을 보이는 것으로 증명이 마무리된다.

 

가장 먼 두 점 구하기

Lemma는 가장 먼 두 점 사이의 거리를 구하는 새로운 알고리즘을 제시해 준다.

 

알고리즘: 볼록 껍질에서, 위와 같은 방법으로 다각형 Q를 만들자. Q에서 마주보는(볼록 껍질의 점의 개수 c에 대해, i번째와 i+c번째) 점의 거리의 절반 중 최대인 것이 가장 먼 두 점 사이의 거리이다.

 

이 방법은 투 포인터를 사용하지 않을 수 있어서, 나의 경우 실수의 여지가 확 줄어드는 좋은 알고리즘이었다. 구현하는 코드는 다음과 같다. 나는 귀찮아서 그냥 STL sort를 사용하였지만, 시계 반대방향 벡터들의 방향과 시계 방향 벡터들의 방향은 각각 단조이므로 병합 정렬로 하면 좀 더 빠를 것이다. 물론 병합 정렬을 하면 아래에서 설명하는 것과 같이, 회전하는 캘리퍼스와 거의 동일한 과정을 거쳐야 한다.

 

회전하는 캘리퍼스와의 관계

조금만 더 고찰해보면, 문제의 풀이에서 정의한 다각형 Q는, P에 대한 회전하는 캘리퍼스 알고리즘의 과정을 하나로 표현한 것임을 알 수 있다. 회전하는 캘리퍼스에서는, 거리가 최대인 점을 찾기 위해 한 점을 고정한 후 다른 점을 그 점과 최대한 반대편에(즉 변에 해당하는 벡터가 평행이고 방향이 반대이게) 놓는 투 포인터 알고리즘을 쓴다. 그런데 변에 해당하는 벡터가 평행이고 방향이 반대인 것은, 변의 반대 방향 벡터가 평행인 것과 같은 말이다. 그러므로, 결국 위의 다각형 Q는 회전하는 캘리퍼스에서 탐색되는 순으로 벡터들을 나열해 놓은 것이다.

위의 내용을 알면, 가장 먼 두 점을 구하는 것에서 거리뿐 아니라 그 두 점이 무엇인지도 바로 구할 수 있다. 최대가 나오는 Q 위의 점의 양쪽 벡터에 해당하는 변이, 회전하는 캘리퍼스가 닿아 있는 곳이다. 그러므로 그 변에서 해당 점에 해당하는 P의 점들에 대해, 거리가 최대인지 확인해주면 된다. 아직 구현은 해보지 않았으나, 어렵지 않게 할 수 있을 것으로 생각한다.

 

이처럼 2006년도에 나온 IMO 문제의 아이디어를 이용해서, Rotating Calipers 알고리즘을 시각화하고 다른 관점에서 살펴볼 수 있다는 점이 신비롭다. 알고리즘이 어떤 값을 구하는 방법을 연구한다면, 수학은 그 값의 성질을 연구한다. 어떨 때는 수학적 성질을 바탕으로 알고리즘이 나오기도 하지만, 이번의 경우에는 알고리즘을 바탕으로 수학적 아이디어를 이용한 풀이가 공식 풀이로 있었다. 비록 알고리즘은 본래 수학의 일부분이지만, 현재 수준에서는 수학 올림피아드에서 다루는 수학 문제들과 정보 올림피아드에서 다루는 알고리즘 문제들은 다소 구분되는 면이 있다. 하지만 이 둘은 결국 하나이고 상호 보완적임을 기억하면서 꾸준히 공부해야겠다고 다짐했다.