Research On Algorithms Of Finding A Simple Path On Given Points In A LR-Visibility Polygon

LR-visibility polygon is one of the main topics in computational geometry field, with significant characters. Many application problems are solved based on LR-visibility polygon with its advantage. The research of this article is not only a further research on LR-visibility polygon but also a new topic of simple path.The simple path problem on given points from the start point s to the end point t in LR-visibility polygon means we need to find a path which is totally inside the LR-visibility polygon and no self-intersection. Besides, each endpoint of the edge in the simple path is one of the given points. The point s and t are also belong to the given points. To solve the simple path problem, based on the relative knowledge of computational geometry, we research on the visibility, LR-visibility polygon, shortest path and simple path, and discuss the relationship of simple path and shortest path, and present and prove the shortest path dependence theorem. At last, we present a greedy algorithm to solve the problem based on Dijkstra algorithm, with the metric of the increasement of link distance, using the skills to judge the intersecting of shortest path. The complexity of the algorithm is O((n2+m)*logm). We finish the algorithm based on some data structure, and test it to prove the algorithm is correct and effective.