A study of algorithms for traveling segment sequences based on convex chain

摘要

In this paper, the problem of traveling disjoint segment sequences in the plane will be studied. The goal is to find the shortest path from the start point, then visiting each segment in the given order, and finally to the target point. By adopting the techniques of division of convex chain, combination optimization and binary search tree, we design a fast algorithm with the O(nlog²n) time complexity to solve it, denoted by BST algorithm, where n is the total number of all segments, and we introduce the main techniques used in this paper in detail. Furthermore, we generate a large amount of test data to test BST algorithm, and compare the efficiency of BST algorithm and Rubber-band algorithm, which is the better solution to this problem. The results show that BST algorithm is superior to Rubber-band algorithm, and it is the optimal algorithm for visiting the disjoint segment sequences so far.