优化TSP算法的完善及推广

A Generalized Algorithm of Optimal Triangulation of Simple Polygon

本文完善和推广了文献［１］中的简单多边形优化三角剖分算法，提出了一种一般化的算法，它能对卷曲、缠绕复杂的简单多边形进行优化三角剖分，我们还把这种算法推广到简单多边形的优化外三角剖分和任意嵌套封闭多边形的情形。

In this paper we present a generalized algorithm of the optimal TSP scheme proposed in [1]. The algorithm is capable of triangulating the arbitrarily sinuous and entangled simple polygon. Its extensions to outer or inner triangulation of simple polygons with or without polygonal holes are also described.