中文摘要：

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

结论摘要：

将最小权三角剖分研究中所提出的问题与我们在研究中发现的新问题进行了系统的整理，指出了几个问题可能的研究突破方向。结合三角剖分局部特征与整体特征之间的差异给出5-最优三角剖分的欧氏几何特征及算法设计，指出了5-最优三角剖分与k-最优三角剖分（k>=6）之间的本质区别。对建筑用料方面提出的具有定长约束条件的Steiner三角剖分问题展开了深入的研究，给出计算该类最优三角剖分的有效近似算法，并证明了所给出的解与最优解之间的近似比。针对Saitou 和 Nei（1999）给出的算法，首先证明了L_∞度量下的边半径的下界为1/6，进一步将该下界提高至1/4（该问题的现有上界为1/4）。由于美国与德国的学者W.Mulzer和G.Rote（2006）证明了最小权三角剖分问题为NP-难问题，我们又展开了占线排序与租赁等优化问题的研究，对加工排序问题中待处理工件可被撤消的情形（该问题已有一个确定性算法其竞争比为5），证明了当所有工件加工时间相同时，该问题的任何确定性策略的竞争比下界是5；针对具有概率特征的占线租赁问题不仅从理论上给出了最优竞争策略与竞争比而且给出了必要的数值计算结果。