问题描述:
1.凸多边形定义:
通常,用多边形顶点的逆时针序列来表示一个凸多边形,
即P={v0 ,v1 ,… ,vn}表示具有n+1条边v0v1,v1v2,… ,vn-1vn,vnv0的一个凸多边形。
若vi与vj是多边形上不相邻的两个顶点,则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形{vi ,vi+1 ,… ,vj}和{vj ,vj+1 ,… ,vi}。
多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。
凸多边形最优三角剖分的问题是:
给定一个凸多边形P={v0 ,v1 ,… ,vn-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。
要求确定该凸多边形的一个三角剖分T,使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数ω。例如:定义 ω(vivjvk)=|vivj|+|vivk|+|vkvj|。(此处的vivjvk是三角形的顶点,与上述定义无关)
2.凸多边形的最优三角剖分有最优子结构性质:
3.最优三角剖分的递归结构:
4.例:
t[ 1 ][ 5 ]=min{ t[ 1 ][ 1 ]+t[ 2 ][ 5 ]+w(v0v1v5);
t[ 1 ][ 2 ]+t[ 3 ][ 5 ]+w(v0v2v5);
t[ 1 ][ 3 ]+t[ 4 ][ 5 ]+w(v0v3v5);
t[ 1 ][ 4 ]+t[ 5 ][ 5 ]+w(v0v4v5); }
t[ 2 ][ 5 ]=min{ t[ 2 ][ 2 ]+t[ 3 ][ 5 ]+w(v1v2v5);
t[ 2 ][ 3 ]+t[ 4 ][ 5 ]+w(v1v3v5);
t[ 2 ][ 4 ]+t[ 5 ][ 5 ]+w(v1v4v5); }
t[ 1 ][ 2 ]=min{ t[ 1 ][ 1 ]+t[ 2 ][ 2 ]+w(v0v1v2); }
......
综上由部分的最优剖分,最终可以得到凸多边形的最优剖分。