最小权三角剖分的计算复杂性和近似算法

求一个给定平面有限点集的最小权三角剖分是一个具有几何结构的组合最优化问题。至今求解最小权三角剖分还没有找到一个多项式算法，也不知道该问题是否为NP-难题。这一问题的计算复杂性、有效近似算法设计和与其相关的最优三角剖分问题是目前组合最优化与理论计算机科学领域中的热点问题。本项目将寻求最小权三角剖分新的组合特征与几何特征，以及局部最优三角剖分的结构特征与求解算法、凸多边形最小权三角剖分的快速求解算法等。并在已有研究成果的基础上探讨最小权三角剖分的计算复杂性、近似算法以及相关最优三角剖分的复杂性与有效算法设计，并完成相关的理论证明和设计可供演示与实用的软件。此项研究及其成果既有重大的理论意义也有一定的应用价值。