[Algorithm] Convex hull 알고리즘

Convex hull 알고리즘은 주어진 점 집합에서 가장 바깥쪽을 감싸는 최소한의 다각형(Convex Polygon)을 찾는 알고리즘입니다. 이 다각형의 내부에는 모든 점이 포함되며, 다각형의 각 내부 각도는 180도 이하입니다. 대표적인 Convex Hull 알고리즘에는 Gift Wrapping (Jarvis March), Graham Scan, Quickhull, Monotone Chain 등이 있습니다. 각각의 알고리즘에 대해 설명해 드리겠습니다.

1. Gift Wrapping (Jarvis March)

이 알고리즘은 왼쪽 가장 아래에 있는 점(시작점)을 선택하여 시작합니다. 시작점에서부터 시계 방향으로 가장 왼쪽에 있는 점을 선택하면서 다각형을 구성합니다.

단계:

1. 시작점(가장 왼쪽 아래에 있는 점)을 찾습니다.
2. 시작점에서부터 가장 왼쪽에 있는 점을 찾습니다.
3. 가장 왼쪽에 있는 점을 새로운 시작점으로 설정하고, 다각형에 포함시킵니다.
4. 다시 새로운 시작점에서 가장 왼쪽에 있는 점을 찾습니다.
5. 시작점으로 돌아올 때까지 2-4 단계를 반복합니다.

복잡도: (O(nh)), 여기서 (n)은 점의 개수, (h)는 Convex Hull의 점의 개수입니다.

2. Graham Scan

이 알고리즘은 점들을 각도 순서대로 정렬한 후, 스택을 이용하여 Convex Hull을 구성합니다.

단계:

1. 가장 아래에 있는 점을 기준점으로 선택합니다. (여러 개라면 가장 왼쪽 점)
2. 다른 모든 점을 기준점과의 각도 순서대로 정렬합니다.
3. 정렬된 점들을 순서대로 처리하면서, Convex Hull의 일부분이 되는 점들을 스택에 저장합니다. 스택에 있는 점들과 새 점을 추가할 때 오른쪽 회전을 하게 되면 스택의 점을 제거합니다.
4. 모든 점을 처리할 때까지 3단계를 반복합니다.

복잡도: (O(n \log n))

3. Quickhull

Quickhull 알고리즘은 퀵소트(Quick Sort)와 유사한 방식으로 작동합니다.

단계:

1. 가장 왼쪽과 가장 오른쪽에 있는 두 점을 찾습니다. 이 두 점을 연결하여 기본 선분을 만듭니다.
2. 이 선분을 기준으로 선분의 왼쪽과 오른쪽에 있는 점들을 분리합니다.
3. 각각의 분리된 집합에 대해 재귀적으로 가장 바깥에 있는 점을 찾고, 새로운 선분을 형성합니다.
4. 더 이상 나눌 점이 없을 때까지 2-3 단계를 반복합니다.

복잡도: 평균 (O(n \log n)), 최악의 경우 (O(n^2))

4. Monotone Chain (Andrew's Algorithm)

이 알고리즘은 점들을 정렬한 후, 상한선과 하한선을 각각 계산하여 Convex Hull을 만듭니다.

단계:

1. 점들을 x좌표 기준으로 정렬합니다.
2. 정렬된 점들로부터 하한선을 만듭니다. (좌측부터 시작하여 스택에 점을 추가하고, 오른쪽 회전이 생기면 스택에서 점을 제거합니다)
3. 다시 정렬된 점들로부터 상한선을 만듭니다.
4. 상한선과 하한선을 합쳐서 Convex Hull을 구성합니다.

복잡도: (O(n \log n))

각 알고리즘마다 장단점이 있으며, 입력 점의 분포에 따라 성능이 다를 수 있습니다. 일반적으로 Graham Scan이나 Monotone Chain 알고리즘이 널리 사용됩니다.

이 알고리즘들을 실제로 구현하여 시각화하면 이해하기 더 쉬울 수 있습니다. 이를 위해 특정 알고리즘의 코드가 필요하시면 말씀해 주세요.