凸多边形的最优三角划分

凸多边形最优三角剖分方法

问题描述
(1) 凸多边形的三角剖分：即将凸多边形划分为若干个互不重叠的三角形，所使用的弦的集合记为T。
(2) 最优剖分：对于给定的凸多边形P，以及定义在由该多边形边与弦构成的三角形上的权重函数w，目标是找到一种三角剖分方式，使得所有被划分出的三角形对应的权重总和达到最小值。
最优子结构性质：
若针对一个具有(n+1)条边的凸多边形P={V0,V1……Vn}，其最优三角剖分T中包含三角形V0VkVn（其中1<=k<=n），则该剖分T的整体权重由三部分组成：即三角形V0VkVn自身的权重、由顶点集合{V0,V1……Vk}构成的多边形对应的权重，以及由顶点集合{Vk,Vk+1……Vn}构成的多边形对应的权重之和。如下图所示：

可以确定，基于T所划分出的两个子多边形的三角剖分方式同样具备最优特性。倘若存在一种权值更小的三角剖分方案，例如{V0,V1……Vk}与{V0,V1……Vk}，则将直接推翻T并非最优三角剖分这一结论，从而产生矛盾。由此可知，凸多边形的三角剖分问题具备最优子结构的特征。
**递推关