A polynomial time algorithm for solving the shortest circuit of China travelling salesman problem

To present a new polynomial time algorithm for China travelling salesman problem, first point set was partitioned into a number of sub-point sets by using convex hull and medial axis. Then the method for solving the convex hulls of sub-point sets and partitioning the remaining subsets was repeatedly used to obtain a sub-path through the sub-point set. Finally, the sub-paths were joined to form a circuit. The time complexity of the new algorithm is O(n²ln(n)). And its application to China travelling salesman problem will give the shortest circuit 15404 km in length. There exists polynomial time algorithm to solve China travelling salesman problem and obtain the shortest circuit.