Development of an Exact Algorithm for Computing Minimum Weight Triangulations

在过去的两年中，我们一直试图发展一个高效的精确算法来计算平面上点的最小权三角剖分（简称MWT）。为此，我们首先开发了一种新的方法来计算有效的下界的长度MWT，根据miniumu的重量匹配的图适当定义为任意两个三角剖分。通过计算实验验证了所提出的下界非常接近于最优，并提出了一个计算MWT的子图LMT骨架的0（n^3logn）算法，对随机生成的点集进行了计算实验，以了解LMT骨架有多大。结果表明，在大多数情况下，LMT骨架是连通的，这意味着MWT可以在实际意义上有效地计算.结合这两种思想，我们提出了一种计算MWT的分支定界算法，并将该算法应用于几个LMT骨架高度不连通的硬实例.计算结果表明，该算法能够计算出这种困难情况下的MWT，并考虑了最大和最小角度分别小于（或大于）或等于给定阈值的角度不变量的MWT计算问题.我们已经开发了一个算法来计算LMT骨架这样的约束MWT。最后，我们制定了结构优化问题，我们遇到的建筑作为一个变种的MWT问题。特别地，我们考虑了在结构特性约束下三角形桁架的拓扑和节点位置的优化问题。

Over the last two yeras, we have tried to develop an efficient exact algorithm for computing a minimum weight triangulation (MWT for short) for points in the plane. For this purpose we have first developed a new way to compute an effective lower bound on the length of MWT,based on the miniumu weight matching of a graph appropriately defined for arbitrary two triangulations. We have verified by computational experimetns that the proposed lower bound is very close to the optimal.We also developed an 0 (n^3logn) algorithm for computing an LMT-skeleton which is subgraph of MWT.We have carried out computational experiments for randomly generated point sets in order to see how large LMT-skeletons are. The results demonstrated that for most cases LMT-skeleton becomes connected, implying that MWT can be computed efficiently in a practical sense.Combining these tow ideas, we then developed a branch and bound algorithm for computing MWT.We have applied our algorithm to several hard instances whose LMT-skeletons are highly disconnected. Computational results showed that the proposed algorithm can compute MWT for such hard instances.We also considered a problem of computing MWT with angular constrants such that maximum and/or minimum angles are less than (resp.larger than) or equal to a given threshold. We have developed an algorithm for computing LMT-skeletons for such constrained MWT.Finally, we formulated structural optimization problems we encounter in architecture as a variant of MWT problems. In particular, we considered a problem of finding and optimal topology and node positions of triangular trusses under the constraint concerning strudtural characteristics.