A Study On The Optimal Algorithms Of Visiting A Sequence Of Geometric Object In The Plane

A kernel problem in computational geometry is to find a shortest route that visits a given discrete geometric object sequence in the plane. The research work involves not only the basic theory about visual recognition, the calculation of shortest path, algorithm design and optimization, but also the abstract models of the robot motion planning, Unmanned Aerial Vehicle control, etc. So, it is quite important in both the theory and the application.Although lots of research results on visiting geometric object sequences have been made, many challenges and problems still need to be solved, such as complex data structures, a large number of iterative calculations, degradation phenomenon for intersection point processing and so on. More efficient algorithms to solve the these problems will be studied in this reseach. The main contributions of the reseach are as following.For the problem of visiting a sequence of disojoint segments, Rubber-band algorithm is a relatively optimal solution and has been widely used. In this thesis, a fast algorithm is proposed which adopts the convex chain to divide the local path and the binary search tree to store local optimal path. The new algorithm has the o(n?~2n) time which can reduce the times of iterations, prevent the oscillation phenomenon with application of Rubber-band algorithm and improve the efficiency of the algorithm. Furthermore, a large of test data generated randomly is used to compare the two algorithms.For the problem of visiting a sequence of segments intersected, an efficient algorithm with O(n~2) time has been presented which adopts the method of crossing over two segments to deal with intersections, and in this algorithm, the adjacent segments order can be changed in order to get the shorter path. The algorithm not only solves the degradation with an application of Rubber-band algorithm, but also can obtain more accurate shortest path. On basis of which, the algorithm of computing the shortest path for visiting lines in given order is studied. In this problem, the method of constructing the convex polygon containing all the intersections of the lines is adopted so that the problem is reduced to compute the shortest path of visiting all the given segments in a convex polygon. A fast solution algorithm is designed with O(n~2) time which is proved the lower bounds of the problem.For the problem of visiting a sequence of disjoint convex polygons, based on the shortest path maps, an improved method to compute the shortest path is proposed which divides the polygons in order and locates the edges in the reverse order. The improved algorithm has the O(kn) time.In this thesis, some key technologies of computing the shotest path of visiting geometric object sequences are discussed and the algorithms proposed are the optimal solution by far, which will be helpful to the solution of practical problems, such as the Watchman Route Problem, robot motion planning and so on. Meanwhile, the thesis also presents the further research work in the field.