货郎担问题的几何解法

GEOMETRIC METHOD FOR SOLVING TS PROBLEM

本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数．

In this paper, a new geometric method for solving TS problem is presented.Let n be the number of points in the point set, and m be the number of vertexes in convex hulls of the point set. The time complexity of the algorithm is: the number of computation distance is O(nm), the number of comparisons is O(max(nm, nlogn) ) and the number of computation included angle is O().