Research On Algorithms Of Euclidean Shortest Paths In Simple Polygons

Euclidean shortest path problem(ESP) is one of the typical problems in Computational Geometry. Its main research topic is to find the shortest path between two points for a given series of obstacles in Euclidean space. This paper wills give a further research to a sub problem of Euclidean shortest path problems, which is Euclidean shortest path problem in a simple polygon.The geometric description of Euclidean shortest path in a simple polygon is finding the shortest path between point s and point t for a given simple polygon P. Algorithms for this problem have many use for solving a lot of problems, such as Watchman Route Problems and Robot motion planning problem etc.When solving ESP in a simple polygon, we will encounter many basic problems of Computational Geometry, such as judging whether two points coincide and the position relationship between two segments. So this paper describes and analyzes these problems, and gives the related solving methods. Then we study the properties of Euclidean shortest path, and have the further research based on Funnel algorithm and Rubberband algorithm, and analyze the time complexity of these algorithms in detail. The focus of the paper is that we give an improved algorithm based on Rubberband algorithm. The improved algorithm introduces the thought of Divide and Conquer, and so we can reduce the scale of the problem, and accelerate the speed of problem solving. At the same time, the paper gives the implementation of Rubberband algorithm and improved algorithm, and we fit the curve of running time of these two algorithms by Subsequent analysis. We solve the equation, and verify the advantage of improved algorithm.