삼각 분할 (동적 계획법) 편집하기

삼각 분할 (동적 계획법)은 볼록 다각형을 삼각형으로 분할하는 과정에서 최소 비용을 구하는 문제를 해결하는 알고리즘 기법이다. 일반적으로 다각형 내부의 삼각형들의 가중치 합이 최소가 되도록 삼각 분할을 수행한다.
==개요==
볼록 다각형의 삼각 분할에서 각 삼각형의 비용이 주어질 때, 최소 비용으로 다각형을 삼각형으로 나누는 문제를 해결하는 알고리즘이다. 이 문제는 동적 계획법(Dynamic Programming, DP)을 활용하여 최적 부분 구조와 중복된 부분 문제를 해결하는 방식으로 접근한다.
==문제 정의==
n개의 꼭짓점을 가진 볼록 다각형 P = (v₁, v₂, ..., vₙ)이 주어졌을 때, 삼각형 (vᵢ, vⱼ, vₖ)의 비용을 c(i, j, k)로 정의한다. 목표는 삼각형 분할을 통해 전체 비용을 최소화하는 것이다.

동적 계획법을 이용하여 최적 부분 문제를 정의하면 다음과 같다.
*'''dp[i][j]''' : 꼭짓점 vᵢ부터 vⱼ까지의 최소 삼각 분할 비용
*점화식:
  dp[i][j] = min(dp[i][k] + dp[k][j] + c(i, k, j))  
  (i < k < j)
==알고리즘==
*삼각 분할 문제를 크기가 작은 부분 문제로 나눈다.
*작은 부분 문제의 최적 해를 이용하여 큰 문제를 해결한다.
*최적 부분 구조와 중복된 계산을 방지하기 위해 DP 테이블을 이용한다.
==예제 코드==
다음은 Python을 이용한 동적 계획법 기반의 최소 비용 삼각 분할 알고리즘이다.<syntaxhighlight lang="python">
import sys

def min_triangulation_cost(points):
    n = len(points)
    dp = [[0] * n for _ in range(n)]

    def cost(i, j, k):
        # 두 점 사이의 거리의 합을 비용으로 가정
        return abs(points[i] - points[j]) + abs(points[j] - points[k]) + abs(points[k] - points[i])

    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            dp[i][j] = sys.maxsize
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost(i, k, j))

    return dp[0][n-1]

# 예제: 볼록 오각형의 꼭짓점 위치
points = [0, 2, 5, 7, 10]
print(min_triangulation_cost(points))
</syntaxhighlight>
==시간 복잡도==
이 알고리즘의 시간 복잡도는 O(n³)이며, 공간 복잡도는 O(n²)이다. 다각형의 변의 개수가 많을수록 계산량이 증가하지만, DP를 활용하여 중복 계산을 줄일 수 있다.
==활용==
*'''컴퓨터 그래픽스''' - 다각형을 삼각형으로 나누어 렌더링 성능을 최적화
*'''지형 모델링''' - GIS에서 지형 데이터를 삼각형으로 분할하여 표현
*'''공학적 최적화''' - 유한 요소법(FEM)에서 삼각 분할을 이용하여 구조 해석
==같이 보기==
*[[동적 계획법]]
*[[삼각 분할]]
*[[델로네 삼각분할]]
*[[볼로노이 다이어그램]]
==참고 문헌==
*de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). ''Computational Geometry: Algorithms and Applications''. Springer.
*Preparata, F. P., & Shamos, M. I. (1985). ''Computational Geometry: An Introduction''. Springer.
[[분류:알고리즘]]