Rearching An Algorithm On ESP Problem Of Visiting Disjoint Segments In The Plane

ESP(Euclidean shortest path) problem is a typical problem in computational geometry. This problem can be simply described as follows:For the given two points and some obstacles in Eculidean space, to find the shortest path between this two points through these obstacles.In this paper, the ESP problem of accessing disordered and disjointed segments set in a plane was studied. The description of this problem is as follows:In a plane, p as the source point and q as the target point, and a n-line segments set S={s1, s2,..., sn), Si∩Sj =φ(1<i,j<n),n>0, asked to find the shortest path from p to q through these segments. This problem is a sub problem of ESP problem. This problem can be used as logical models of many practical problems, such as two-dimensional pattern recognition, robot motion planning, image analysis, inspector, etc.A lot of basic knowledge of computational geometry and algorithms will be encountered in solving the ESP problem. So, this paper firstly studied the basic knowledge and algorithms of computational geometry. The judgment of segment intersects, connected graph, spanning tree, triangulation and the dual graph were mainly studied. Subsequently, the Rubberband algorithm and its improved algorithm were studied. These two algorithm can be used for solving the ESP problems of accessing ordered and disjointed segments in a plane. Then, a new algorithm was proposed in this paper. This new algorithm used the idea of the minimum spanning tree to slove the ESP problem which needed to be sloved in this paper. After analyzing the new algorithm, the result showed that the time complexity of this algorithm was O(n3). At last, this new algorithm was verified by experiments. The "running time-the number of segments" curve was be drawed. The running time and results of this algorithm were compared to the results of brute-force method using comparative analysis. The comparative results showed that the results of this algorithm was credible within the range of allowable error. This algorithm can find a approximate optimal solution of ESP problem in polynomial time complexity.The focus of this paper is to determine the order of the segments. The mehod of constructing minimum spanning tree and traversing the tree was mainly used.