최소둘레 삼각형

점들을 $x$좌표 순서로 정렬하고 분할 정복을 적용한다.

현재 점 집합을 왼쪽 절반과 오른쪽 절반으로 나눈 뒤, 각 절반에서 최소 둘레를 재귀적으로 구한다. 두 값의 최솟값을 $\delta$라 하자. 이제 양쪽 절반의 점을 모두 사용하는 삼각형 중 둘레가 $\delta$보다 작은 것이 있는지만 확인하면 된다.

둘레가 $\delta$보다 작은 삼각형의 모든 변의 길이는 $\frac{\delta}{2}$보다 작다. 한 변의 길이를 $a$, 나머지 두 변의 길이를 $b,c$라 하면 세 점이 한 직선 위에 있지 않으므로

$$a<b+c$$

이고, 따라서

$$2a<a+b+c<\delta$$

이다.

양쪽 절반의 점을 모두 사용하는 삼각형을 생각하자. 서로 다른 절반에 속한 두 꼭짓점의 거리가 $\frac{\delta}{2}$보다 작으므로, 세 꼭짓점은 모두 분할선으로부터 수평 거리 $\frac{\delta}{2}$ 미만인 띠 안에 있다. 또한 모든 변의 길이가 보다 작으므로 세 꼭짓점의 좌표 범위도 보다 작다.

따라서 분할선 주변의 띠에 속한 점들을 $y$좌표 순서로 정렬하고, $y$좌표 차이가 $\frac{\delta}{2}$보다 작은 점들끼리만 확인하면 된다.

이 범위에 들어오는 점의 개수는 상수이다. 띠 안에서 높이가 $\frac{\delta}{2}$인 임의의 수평 구간을 생각한다. 분할선의 왼쪽과 오른쪽은 각각 너비와 높이가 모두 $\frac{\delta}{2}$ 이하인 직사각형이다.

각 직사각형을 가로로 $2$등분하고 세로로 $3$등분한다. 작은 직사각형 하나의 너비는 $\frac{\delta}{4}$, 높이는 $\frac{\delta}{6}$이므로 대각선 길이는

$$\sqrt{\left(\frac{\delta}{4}\right)^2+\left(\frac{\delta}{6}\right)^2} = \frac{\sqrt{13}}{12}\delta$$

이다.

같은 작은 직사각형 안에 같은 재귀 절반에 속하는 점이 세 개 있다면, 그 세 점으로 만든 삼각형의 둘레는

$$3\cdot\frac{\sqrt{13}}{12}\delta = \frac{\sqrt{13}}4\delta <\delta$$

이다. 이는 해당 재귀 절반에서 구한 최소 둘레가 $\delta$ 이상이라는 사실에 모순이다.

따라서 작은 직사각형마다 점은 최대 두 개이다. 한쪽에는 작은 직사각형이 $6$개 있으므로 최대 $12$개, 양쪽을 합치면 최대 $24$개의 점만 존재한다.

결국 띠의 점들을 $y$좌표 순서로 보면서, 각 점 뒤의 상수 개 점으로 만들 수 있는 모든 삼각형을 확인하면 된다. 세 점이 모두 같은 재귀 절반에 속하면 이미 재귀 호출에서 확인했으므로 생략한다.

구현에서는 둘레를 직접 계산하기 전에 세 변의 제곱거리가 모두 $\left(\frac{\delta}{2}\right)^2$보다 작은지 먼저 검사한다. 이 조건을 통과한 경우에만 제곱근을 계산하면 상수를 크게 줄일 수 있다.

각 재귀 단계에서 두 절반의 $y$좌표 정렬 결과를 선형 시간에 병합한다. 따라서 전체 시간 복잡도는

$$O(N\log N)$$

이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6