A Study Of Solving L1 Problem By Visiting Disjoint Line Segments In The Plane

L1 Problem is one of the most important problems of computational geometry. Researching on the character of L1 distance, it can help people develop the effective algorithm of these classic problems. Therefore, the research on the L1 distance problem has not only the theoretical significance, but also the practical value.Based on the L1 distance study of the issue, This paper discusses the theory of the shortest path, and give the algorithm of shortest L1 path problem by using the idea of divide plane, and prove strictly its suitability. Through the analysis of the location of points and line segments,givening simple feature of L1 path. Based on these characteristics, this paper presents a built of flat space division algorithm with time complexity O (n), the algorithm of shortest path and algorithm of solve the problem L1, can be computed in linear time, starting from the starting point s,touring a k sequence line segments, and ultimately reach the target point t, the shortest distance L1. This greatly simplifies the solution process.In order to verify the feasibility and effectiveness of the algorithm, this paper for test data point out the shortest path and the results map, and gives the shortest path length L1, the final results of the algorithm was run analysis. The results show that the given algorithm is not only efficient but also practical.