Research On Algorithms Of ESP Problem That Reaches A Sequence Of Segments In The Plane

Euclidean shortest path problem is called as ESP for short, it is one of the typical problems in Computational Geometry. This paper will give a research to ESP problem that reaches a sequence of segments in the plane, with the emphasis on the situation that there exists maybe the crossing segments in a set of ESP. This problem is an abstract model of lots of practical applications, so there is a great significance on the research for this problem.At first, this paper will analyze the characteristics of ESP problem that reaches a sequence of segments in the plane. For the basic knowledge about Computational Geometry, Trapezoidal split and Triangulation for a simple polygon in relation to this problem, it will give a further description, and analyze Rubberband algorithm and its characteristics. On this basis, this paper will discuss the degenerate phenomenon in detail that will maybe appear when Rubberband algorithm deals with this problem for adjacent segments intersecting in a set of ESP, and give the related solving methods for it. Bringing the thought of Divide and Conquer and improving Rubberband algorithm make it adequate for the ESP problem in this paper. After giving the improvement program, this paper will design the related data structures, finish the implementation of Rubberband algorithm and test this algorithm through producing lots of random testing data. And give the running results and illustrate Euclidean shortest path. At last, we will analyze the time complexity of these two algorithms and the related conclusion by Subsequent analysis, in order to verify the advantage of improved algorithm.This research work has gotten the support of National Natural Science Foundation of China.