凸多边形最优三角剖分

凸多边形最优三角剖分-动态规划

问题描述

给定凸多边形P={v0，v1，… ，vn-1}，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权，即三角剖分中诸三角形上权之和为最小。

问题分析

  1. 若凸(n+1)边形P={v0,v1,…,vn}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和
  2. 由T所确定的这2个子多边形的三角剖分也是最优的。
  3. 因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。

算法原理

定义$t[i][j]，1≤i<j≤n$为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。

为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。

t[i][j]的值可以利用最优子结构性质递归地计算。当j-i≥1时，凸子多边形至少有3个顶点。

由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。

由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置。

$$
t[i][j]=min{t[i][k]+t[k+1][j]+w(v[i-1]v[k]v[j])}
$$

算法复杂度

  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^2)$

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void MinWeightTriangulation(int n，int **t，int **s) {
    for (int i = 1; i <= n; i++) t[i][i] = 0;
    for (int r = 2; r <= n; r++)
        for (int i = 1; i <= n - r+1; i++) {
            int j = i+r-1;
            t[i][j] = t[i+1][j]+ w(i-1, i, j);
            s[i][j] = i;
            for (int k = i+1; k < j; k++) {
                int u = t[i][k] + t[k+1][j] + w(i-1, k, j);
                if (u < t[i][j]) { t[i][j] = u; s[i][j] = k;}
            }
        }
}