Development of an Exact Algorithm for Computing Minimum Weight Triangulations

在过去的两年里，我们一直试图开发一种有效的精确算法来计算平面上点的最小权三角剖分(简称MWT)。为此，我们首先发展了一种新的方法来计算MWT长度的有效下界，该方法基于任意两个三角剖分的适当定义的图的最小umu权匹配。通过计算实验验证了提出的下界非常接近最优值，并提出了一种0(n^3logn)算法来计算MWT子图的LMT-骨架，并对随机生成的点集进行了计算实验，以了解LMT-骨架有多大。结果表明，在大多数情况下，LMT-骨架是连通的，这意味着可以在实际意义上有效地计算MWT。结合这两个思想，我们提出了一种计算MWT的分枝定界算法，并将我们的算法应用于LMT-骨架高度不连通的几个硬实例。计算结果表明，该算法能较好地计算复杂情况下的MWT，并考虑了具有角度约束且最大和/或最小角度小于(或大于)或等于给定阈值的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.