[6기 강남 조유석] Convex Hull

안녕하세요. 강남멤버십 23-1기 조유석입니다.

이번 포스팅에서는 계산 기하의 문제 중 하나인 Convex Hull 에 대해 알아보겠습니다.

Convex Hull

Convex Hull 이란 2차원 평면에서 주어진 점들을 모두 포함하는 최소 크기의 다각형을 말합니다. 아래 그림은 주어진 점들의 Convex Hull 을 보여줍니다. 크기가 최소여야 하기 때문에 Convex Hull 의 꼭지점이 모두 원래 주어진 점이라는 것을 알 수 있습니다.

Cross Product

Convex Hull 을 구하기 위해 먼저 벡터의 외적 개념에 대해 알아보겠습니다. Cross Product. 벡터의 외적은 사실 두 개의 3차원 벡터에 대해 정의되는 연산으로, 3차원 벡터 a, b가 주어졌을 때 이 두 벡터에 모두 수직인 다른 벡터를 반환합니다. 하지만 모든 2차원 벡터는 사실 z 좌표가 0인 3차원 벡터로 생각할 수 있기 때문에, 2차원 벡터에 대해서도 외적을 정의할 수 있습니다.

이 Cross Product 에서 유용한 것은 반환되는 벡터의 길이와 방향입니다. 2차원 벡터 와 의 외적 의 길이는 다음과 같이 계산할 수 있습니다.

외적은 어느 방향으로 계산하느냐에 따라 그 부호가 달라집니다. 이유는 에서 가 단순히 두 벡터의 사이각이 아니라 a에서 b까지 반시계 방향으로 얼마나 회전해야 하는가를 나타내기 때문입니다. 이기 때문에, 외적이 음수인지 양수인지를 알면 가 양수인지 음수인지 쉽게 알 수 있습니다. 

외적의 주된 사용처는 바로 이와 같은 성질을 이용해 두 벡터의 방향성을 판단하는 것입니다.

- : b가 a로부터 반시계 방향(180도 이내)

- : b가 a로부터 시계 방향(180도 이내)

Graham Scan Algorithm

Convex Hull 은 아주 잘 알려진 기하 문제로, 서로 다른 시간 복잡도를 갖는 여러 Convex Hull 알고리즘이 개발되어 있습니다. 여기에서는 그 중 O(n log n) 시간복잡도를 갖는 Graham Scan Algorithm 에 대해 알아보겠습니다.

Grahams Scan Algorithm 은 세 점으로 이루어지는 삼각 형 내에 어떤 점이 포함되면 이 점은 Convex Hull 에 포함되는 점이 될 수 없다는 성질을 이용합니다. 자세한 과정을 아래에서 살펴보도록 하겠습니다.

1. 가장 아래에서 가장 오른쪽에 있는 점(rightmost lowest point)을 찾습니다.(이 점은 반드시 Convex Hull 에 포함되는 점입니다.) 이 점을 기준으로 각 점들을 각도순으로 정렬합니다.

2. rightmost lowest point 와 그 다음 위치에 오는 점을 스택에 push 합니다.

3. 스택의 두 개의 점과 다음 위치에 오는 점 간의 외적을 구합니다. 이 때, 결과가 반시계 방향이면 다음 위치의 점을 스택에 push, 시계 방향이면 스택에서 pop 을 합니다.

4. 모든 점에 대해서 3번 과정을 반복합니다.

최근에 출제된 문제 중에는 ACM-ICPC Asia Regional Daejeon Site 2014 인터넷 예선에서 Convex Hull 을 이용해 푸는 문제가 출제되었습니다.(Problem E: Highway)

http://acm.kaist.ac.kr/2014/CONTEST/problemset.pdf

공부하고 풀어보시는 것도 좋을 것 같습니다.

이상으로 Convex Hull 에 대해 알아보았습니다.

감사합니다.

Reference

  - http://www.dovelet.com

  - ‘프로그래밍 대회에서 배우는 알고리즘 문제해결 전략’ - 구종만 저